2024-05-15-LeetCode-239-滑动窗口最大值.md

发表于 | 分类于

题目说明

滑动窗口每滑动固定步长k，则左边届有k个元素从窗口中移除，右边界有k个元素被添加到窗口中。

针对滑动窗口的题目，暴力算法就是对每个窗口单独计算一次，这个算法很容易超时，因此常规技巧是：只计算窗口发生变化的数据。

这个思路针对easy或者medium的题目一般都是有效的，但是复杂题目往往会设置条件阻碍边界元素的计算，使得窗口滑动导致的元素变化不好处理，就类似今天这个题目。

LeetCode 239 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。

1
2
3
4
5
class Solution {

  public int[] maxSlidingWindow(int[] nums, int k) {
  }
}

直观思路

题目还是很好理解的，没有出现的复杂的描述。只需要推动滑动窗口走完整个数组，并且计算出来每个窗口中的最大值即可。

参照对滑动窗口的理解，已知步长是k，每次滑动一个单位。那么很容易有：

  • 针对第一个k窗口，需要完整遍历窗口的元素，获得最大值，放入结果数组
  • 之后每滑动一步，剔除最左侧数据，加入最右侧数据，也就是只要最左侧数据不是上一个窗口的最大值，那么就直接比较右侧新加入的数据和目前的最大值，然后把新的最大值放入数组
  • 窗口推动至数组的最后一位，解题完成

但是这个直观的思路忽略了一个非常麻烦的问题，那就是：如果剔除的数据刚好就是上一个窗口的最大值，这种情况如何计算呢？

假如我们针对这个case使用暴力解法，认为这是一个小概率事件，在遇到这个case的时候遍历一次窗口，似乎也说得过去，那么得到这个算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {

  public int[] maxSlidingWindowSlow(int[] nums, int k) {
    List<Integer> ans = new ArrayList<>();
    if (nums.length == 0 || k == 0) {
      return new int[]{};
    }
    if (k == 1) {
      return nums;
    }
    int leftIndex = 0;
    int maxValue = nums[0];
    for (int i = 0; i < k; i++) {
      maxValue = Math.max(maxValue, nums[i]);
    }
    ans.add(maxValue);
    for (int i = k; i < nums.length; i++) {
      if (nums[leftIndex] == maxValue) {
        maxValue = Integer.MIN_VALUE;
        for (int j = leftIndex + 1; j <= i; j++) {
          maxValue = Math.max(maxValue, nums[j]);
        }
      } else {
        maxValue = Math.max(maxValue, nums[i]);
      }
      ans.add(maxValue);
      leftIndex++;
    }
    int[] res = new int[ans.size()];
    for (int i = 0; i < ans.size(); i++) {
      res[i] = ans.get(i);
    }
    return res;
  }
}

基于测试case验证一下这个算法，每个都能通过。但是既然这个算法标了hard，提交是肯定不能通过的，因为超大的测试case会直接时间超限，只能老实研究优化的问题。

使用优先队列解答题目

在第一版的直觉代码中，需要解决的是特殊case下的双重循环：

1
2
3
4
5
6
7
8
9
10
11
12
 for (int i = k; i < nums.length; i++) {
      if (nums[leftIndex] == maxValue) {
        maxValue = Integer.MIN_VALUE;
        for (int j = leftIndex + 1; j <= i; j++) {
          maxValue = Math.max(maxValue, nums[j]);
        }
      } else {
        maxValue = Math.max(maxValue, nums[i]);
      }
      ans.add(maxValue);
      leftIndex++;
    }

当左边被抛弃的元素刚好就是最大元素时，没办法从快速已知窗口中找到第二大的元素，所以导致需要从做窗口的位置开始遍历窗口内的元素。

那么直观的思路就是：

  • 如果我能快速的找到窗口内最大的元素，那么就不需要每次遍历

优先队列在这个时候就非常的好用，完美的匹配的这个场景。

复习一下优先队列的基本概念：

  • 队列中的元素根据优先级排序，高优先级的元素最先出队，优先级的实现可以自定义
  • 优先队列基于堆实现，时间复杂度是O(log n)

如果使用优先队列的特点，把K窗口内的数据都放入优先队列，每次需要检查的时候弹出最大元素，那就能以O(log n) 的代价获得窗口内的最大元素，时间上应该就不会有问题。

但是为了确定最大元素是否在窗口内，需要确认一下弹出元素的下标，因此需要在队列中存储一下元素在nums数组中的下标。

伪代码如下：

  • 创建一个优先队列用于存储数组中的元素，为了能够存储元素和元素对应的下标，把类型存成数组，index0存元素，index1存下标
  • 遍历数组的0->k-1位置，创建k个一维数组，index0存元素，index1存下标，放到队列里
  • 把答案数组声明出来，长度是k-n+1，答案数据的第一个元素就是优先队列的top元素，先塞进去
  • 遍历数组剩下的内容，每一个元素都放进队列里
  • 检查队列的顶部元素的下标是不是在窗口的左边，是的话就把元素删掉
  • 然后把新的符合窗口内部范围的元素加到返回答案里
  • 直到遍历结束，返回答案

注意点：

  • 一维数组比map省空间，所以队列里面放一维数组，对应的，优先级比较方法需要自己重新实现
  • 检查元素的时候的时候不要直接poll，先peek出来看看是不是需要剔除，不然还要加回去
  • 因为每次只检查队列里面最大的元素，如果最大元素在k窗口内，那么不会继续检查，所以优先队列其实会存一些不在窗口内的数据，但是显然对答案的生成没有影响

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {

  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(
        (pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
    for (int i = 0; i < k; ++i) {
      priorityQueue.offer(new int[]{nums[i], i});
    }
    int[] ans = new int[n - k + 1];
    ans[0] = priorityQueue.peek()[0];
    for (int i = k; i < n; ++i) {
      priorityQueue.offer(new int[]{nums[i], i});
      while (priorityQueue.peek()[1] <= i - k) {
        priorityQueue.poll();
      }
      ans[i - k + 1] = priorityQueue.peek()[0];
    }
    return ans;
  }
}

如果使用这个解法，导致时间复杂度上升到O(n*n)的双重循环就被优化掉了，新的算法的时间复杂度是O(n log n) ，满足要求。

单调队列

单调队列在解决滑动窗口最大值或者最小值问题上，非常的专业对口。

首先来看一下单调队列的定义：

  • 分为单调递增或者单调递减队列，队中的元素从小到大或者从大到小排列；
  • 经常用双端队列（Deque）维护，支持从头部或者尾部直接操作队列内的元素
  • 单调性的维护：插入元素的时候如果元素不满足单调性，那就把元素删掉

如果基于单调队列重新来考虑这个问题。

优先队列解法中的注意点提到，我们并不关注队列中有多少元素是窗口外的，只要最大的元素位于窗口内，那么就能得到想要的结果。那么在滑动窗口最大值问题中，我们真正关心的是什么？

我们关心的真正问题是：窗口内哪一个index是当前窗口的最大值。

使用优先队列可以认为我们在对所有遍历过的数字进行排序，但实际上并不需要对所有的值排序，只要我们能够检查当前最大值是不是在窗口内，那么就无需关心其他的数据。

由于单调队列在这个问题上也属于公式题了，直接上伪代码：

  • 声明双端队列用于单调队列的维护
  • 遍历0->k-1的元素，对于任意一个元素num[i] ，和队列中最小的元素比较：如果大于队列最小的元素，那么就删除最小元素，比较新的最小元素，直到nums[i] 成为队列中最小的元素
  • 将队列中最大的元素加入答案数组，这个元素就是k窗口 0->k-1 内的最大元素
  • 然后继续遍历数组：
    • 对于任意一个元素num[i] ，和队列中最小的元素比较：如果大于队列最小的元素，那么就删除最小元素，比较新的最小元素，直到nums[i] 成为队列中最小的元素
    • num[i]放入队列后，需要从队列中获得最大值放入ans，此处需要检查最大值的index是否还在k窗口内，如果不在就移除队列，直到符合要求

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {

  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < k; i++) {
      while (deque.size() != 0 && nums[i] >= nums[deque.peekLast()]) {
        deque.pollLast();
      }
      deque.offerLast(i);
    }
    ans[0] = nums[deque.peekFirst()];
    for (int i = k; i < nums.length; i++) {
      while (deque.size() != 0 && nums[i] >= nums[deque.peekLast()]) {
        deque.pollLast();
      }
      deque.offerLast(i);
      while (deque.peekFirst() <= i - k) {
        deque.pollFirst();
      }
      ans[i - k + 1] = nums[deque.peekFirst()];
    }
    return ans;
  }
}