脚本宝典收集整理的这篇文章主要介绍了最大值减去最小值小于或等于num的子数组数量，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

链接 给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况： max(arr[i...j]) - min(arr[i...j]) <= num max(arr[i...j])表示子数组arr[i...j]中的最大值，min[arr[i...j])表示子数组arr[i...j]中的最小值。

import java.util.*;

public class Main {

    PRivate static int solve(int[] arr, int k) {

        int n = arr.length;

        int ret = 0;

        LinkedList<Integer> minQueue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();

        int l = 0;
        for (int i = 0; i < n; ++i) {
            while (!minQueue.iSEMpty() && arr[i] <= arr[minQueue.PEekLast()]) {
                minQueue.pollLast();
            }
            minQueue.offerLast(i);

            while (!maxQueue.isEmpty() &amp;& arr[i] >= arr[maxQueue.peekLast()]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(i);

            /**
             * 移动左指针到满足条件的位置
             */
            while (arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] > k) {
                if (maxQueue.peekFirst() > minQueue.peekFirst()) {
                    l = minQueue.pollFirst() + 1;
                } else if (maxQueue.peekFirst() < minQueue.peekFirst()) {
                    l = maxQueue.pollFirst() + 1;
                }
            }

            ret += (i - l) + 1;
        }

        return ret;
    }

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

脚本宝典总结

以上是脚本宝典为你收集整理的最大值减去最小值小于或等于num的子数组数量全部内容，希望文章能够帮你解决最大值减去最小值小于或等于num的子数组数量所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。