题解 | #最大值减去最小值小于或等于num的子数组数量

最大值减去最小值小于或等于num的子数组数量

https://www.nowcoder.com/practice/5fe02eb175974e18b9a546812a17428e

import java.util.Scanner;

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int num = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(getNum(arr, num));
        }
    }

    public static int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0; // 检查数组是否为空或长度为0
        }
        LinkedList<Integer> qmin = new LinkedList<>(); // 存储最小值的双端队列
        LinkedList<Integer> qmax = new LinkedList<>(); // 存储最大值的双端队列
        int i = 0; // 子数组的起始位置
        int j = 0; // 子数组的结束位置
        int res = 0; // 满足条件的子数组计数

        while (i < arr.length) { // 遍历数组
            while (j < arr.length) { // 扩展子数组的右边界
                //qmin 队列是一个单调递增队列,队列的最后一个元素(peekLast())是队列中最近添加且最大的元素。
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                    qmin.pollLast(); // 更新最小值队列
                }
                qmin.addLast(j);
                //qmax 队列是一个单调递减队列,队列的最后一个元素(peekLast())是队列中最近添加且最小的元素。
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                    qmax.pollLast(); // 更新最大值队列
                }
                qmax.addLast(j);
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break; // 如果当前子数组不满足条件,则退出内层循环
                }
                j++; // 扩展右边界
            }
            if (qmin.peekFirst() == i) {
                qmin.pollFirst(); // 移除过期的最小值
            }
            if (qmax.peekFirst() == i) {
                qmax.pollFirst(); // 移除过期的最大值
            }
            res += j - i; // 对于每一个以 i 开始的位置,从 i 到 j-1 的所有子数组都满足条件
            i++; // 移动左边界
        }
        return res; // 返回满足条件的子数组总数
    }

}

这段 Java 代码实现了查找数组中最大值减去最小值小于或等于 num 的所有子数组的数量。下面是代码的逐行解释:

  1. 检查数组有效性:如果输入的数组为空或长度为零,直接返回0。
  2. 初始化两个双端队列:qmin 用于维护子数组的最小值,qmax 用于维护子数组的最大值。
  3. 初始化变量:i 和 j 分别作为子数组的左右边界,res 用于统计满足条件的子数组数量。
  4. 外层循环:通过变量 i 遍历数组,代表子数组的起始位置。
  5. 内层循环:通过变量 j 扩展子数组的右边界。使用双端队列更新子数组的最大值和最小值。如果当前子数组的最大值和最小值的差大于 num,则停止内层循环。
  6. 更新队列:如果队列头部元素是子数组的起始位置,则将其移除。
  7. 计算子数组数量:将 j - i 加到 res 上,这表示以 i 为起始位置,有 j - i 个子数组满足条件。
  8. 移动左边界:增加 i,以检查下一个可能的子数组。
  9. 返回结果:所有满足条件的子数组数量。

通过这种方法,代码有效地计算了所有满足 "最大值减去最小值小于或等于 num" 条件的子数组数量。

全部评论

相关推荐

10-07 23:57
已编辑
电子科技大学 Java
八街九陌:博士?客户端?开发?啊?
点赞 评论 收藏
分享
喜欢走神的孤勇者练习时长两年半:池是池,发是发,我曾池,我现黑
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务