小编点评

**算法思路：** 1. 使用两个链表 `qMax` 和 `qMin` 来记录最大值和最小值的下标。 2. 遍历数组 `arr`，对于每个元素，如果 `max(arr[i...j])` 大于 `min(arr[i...j])`，则将 `r` 赋值给 `qMax` 的末尾，并将 `r` 添加到 `ans` 中。 3. 如果 `qMax` 的首部位置与 `l` 相等，则将 `qMax` 的首部元素（最大值）从 `qMax` 中移除，并将 `l` 更新到 `qMax` 的首部位置。 4. 如果 `qMin` 的首部位置与 `l` 相等，则将 `qMin` 的首部元素（最小值）从 `qMin` 中移除，并将 `l` 更新到 `qMin` 的首部位置。 5. 如果 `r` 的值大于 `num`，则跳出循环，因为 `r` 超出了有效范围。 6. 返回 `ans` 的值。 **时间复杂度：**O(n)，其中 n 是数组长度。 **空间复杂度：**O(n)，因为我们使用两个链表来记录最大值和最小值的下标。 **示例：** **输入：** ``` 5 1 2 3 4 5 ``` **输出：** ``` 4 ``` **解释：** 数组的有效子数组有 4 个，因为最大值在数组的第 2 和 4 个位置出现，最小值在数组的第 1 和 3 个位置出现。

正文

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

作者：Grey

原文地址：

博客园：最大值减去最小值小于或等于 num 的子数组数量问题

CSDN：最大值减去最小值小于或等于 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]中的最小值。

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

思路

本题可以用滑动窗口算法来解，算法说明见：滑动窗口最大值问题

根据题目意思，我们可以得到如下三个结论

第一个结论：arr[L..R]达标，则 arr 中内部的任何一个子数组都达标；

第二个结论：arr[L..R]不达标，则 arr 扩充后肯定也不达标；

第三个结论：L...R 范围如果达标，其子数组个数为：R - L。

利用滑动窗口算法，我们可以得到必须以l位置作为左边界的情况下，有多少达标的数组。

完整代码如下（含对数器）

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


public class Main {
  public static int getNum(int[] arr, int num) {
    LinkedList<Integer> qMax = new LinkedList<>();
    LinkedList<Integer> qMin = new LinkedList<>();
    int ans = 0;
    int l = 0;
    int r = 0;
    while (l < arr.length) {
      while (r < arr.length) {
        while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[r]) {
          qMax.pollLast();
        }
        qMax.addLast(r);
        while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[r]) {
          qMin.pollLast();
        }
        qMin.addLast(r);
        if (arr[qMax.peekFirst()] - arr[qMin.peekFirst()] > num) {
          break;
        }
        r++;
      }
      // r是以l作为左边界，第一个不满足条件的位置
      ans += (r - l);
      // 弹出过期位置
      if (!qMax.isEmpty() && qMax.peekFirst() == l) {
        qMax.pollFirst();
      }
      // 弹出过期位置
      if (!qMin.isEmpty() && qMin.peekFirst() == l) {
        qMin.pollFirst();
      }
      l++;
    }
    return ans;
  }

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

更多

算法和数据结构笔记