算法通关村第十六关黄金挑战——求滑动窗口中的最大值（滑动窗口与堆方法、双端队列法和直接比较法）

大家好，我是怒码少年小码。

今天这篇就讲一道题目，不难😎，但是一定要学会自己思考。

滑动窗口最大值

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

示例 1：

• 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
• 输出：[3,3,5,5,6,7]

解释：滑动窗口的位置 __ 窗口内的最大值

• [1 3 -1] -3 5 3 6 7 _______ 3
• 1 [3 -1 -3] 5 3 6 7 _______ 3
• 1 3 [-1 -3 5] 3 6 7 _______ 5
• 1 3 -1 [-3 5 3] 6 7 _______ 5
• 1 3 -1 -3 [5 3 6] 7 _______ 6
• 1 3 -1 -3 5 [3 6 7] _______ 7

直接比较法

首先，我第一个想到的是滑动窗口+直接比较的方法，既然是求每次滑动窗口的最大值，那就维护两个指针，当两个指针每次移动的时候都求一下当前窗口内的最大值，求出后放到存放最大值的数组中。这样一直到右指针到达数组的末尾。

public int[] maxSlidingWindow(int[] nums, int k) {
  int left = 0;
  int right = k - 1;
  int len = nums.length- k + 1 ;
  int[] maxList = new int[len];
  while(right < nums.length){
      int max = nums[left];
      for(int i = left ; i <= right ; i++ ){
          if(nums[i] > max){
              max = nums[i];
          }
      }
      maxList[left] = max;
      left++;
      right++;
  }
  return maxList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当然，很不幸，这种方法超出了时间限制😎🤏🕶 -> 😭。接下来讲的方法才是本篇的重点。

滑动窗口与堆

本题初始时，我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素num 在数组中的下标为index。

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    //定义优先级队列，自定义排序器，首先按照nums元素值进行降序排序，如果元素值相等，则按照数组下标值进行降序排序
    PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
        public int compare(int[] pair1 , int[] pair2){
            return pair1[0] != pair2[0] ? pair2[0]-pair1[0]:pair2[1]-pair1[1];
        }
    });
      // 前k个元素入队
    for(int i =0;i < k ; i++){
        pq.offer(new int[]{nums[i],i});
    }
    // 初始化结果数组
    int[] ans = new int[n - k + 1];
    ans[0] = pq.peek()[0];
    // 开始滑动窗口
    for(int i = k ; i < n ; i++){
        // 新的元素入队
        pq.offer(new int[]{nums[i],i});
        // 因为已经排好序，因此可以通过peek剔除掉当前队列中为最大值但非窗口中的的元素，循环结束后则队首元素为当前队列中为最大值且是窗口中的元素
        while(pq.peek()[1] <= i - k){
            pq.poll();
        }
        ans[i - k + 1] = pq.peek()[0];
    }
    return ans;
}
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

首先，我们有一个整数数组 nums 和一个窗口大小 k。我们需要找到每个窗口中的最大值，并将这些最大值存储在一个新的数组 ans 中。

代码的核心是使用优先队列（PriorityQueue）来维护窗口中的元素，并根据它们的值和索引进行比较。

首先，我们创建一个优先队列 pq，并通过传入一个自定义的比较器来定义元素的比较规则。比较器中的比较规则是根据元素的值和索引进行比较，如果元素的值不相等，则按值的降序排列，如果元素的值相等，则按索引的降序排列。

接下来，我们遍历数组 nums 的前 k 个元素，并将它们添加到优先队列 pq 中。每个元素都是一个数组，包含元素的值和索引。

new int[]{nums[i], i} 是一个匿名整数数组对象的创建和初始化。它的作用是创建一个包含两个元素的整数数组，并将 nums[i] 赋值给数组的第一个元素，将 i 赋值给数组的第二个元素。

在这个特定的代码中，我们使用 new int[]{nums[i], i} 来创建一个包含当前元素值 nums[i] 和当前索引 i 的整数数组。然后，我们将这个数组添加到优先队列 pq 中，以便在后续的操作中使用。

然后，我们创建一个新的数组 ans，用于存储每个窗口的最大值。我们首先将优先队列 pq 中的最大元素的值存储在 ans 的第一个位置。

接下来，我们从第 k 个元素开始遍历数组 nums。对于每个元素，我们将其添加到优先队列 pq 中，并执行以下操作：

1. 检查优先队列 pq 的顶部元素（最大元素）的索引是否在当前窗口范围内。如果不在范围内，说明该元素已经不在当前窗口中，我们需要将其从优先队列 pq 中移除。我们反复执行此操作，直到顶部元素的索引在当前窗口范围内。

2. 将优先队列 pq 的顶部元素的值存储在 ans 数组中的相应位置。这个值就是当前窗口的最大值。

重复以上步骤，直到遍历完整个数组 nums。

最后，我们返回数组 ans，其中包含了每个窗口的最大值。

双端队列

这种方法就当是一个小扩展

第一种方法在每个窗口内通过遍历查找最大值，时间复杂度为 O(k)。可以使用双端队列（Deque） 来优化这个过程，将当前窗口内的较小元素从队列中移除，以保持队列的头部始终是窗口内的最大值的下标。这样可以将时间复杂度降低到 O(1)。

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0) return new int[0];
    
    Deque<Integer> deque = new ArrayDeque<>();
    int[] maxList = new int[n - k + 1];
    for (int i = 0; i < nums.length; i++) {
        // 移除超出窗口范围的元素
        if (!deque.isEmpty() && deque.peek() < i - k + 1) {
            deque.poll();
        }
        // 移除窗口内小于当前元素的元素，保持队列头部始终是最大值
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        //队列中加入数组的下标
        deque.offer(i);
        // 将窗口内的最大值存储在结果数组中
        if (i - k + 1 >= 0) {
            maxList[i - k + 1] = nums[deque.peek()];
        }
    }
    return maxList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

小码补充：

防止有人不了解Java中的双端队列，这里我们做一个简单的知识补充

在Java中，Deque 接口是双端队列（Double Ended Queue）的一种实现。Deque 具有队列和栈的性质，可以在队列的两端进行插入和删除操作。下面逐一解释 Deque 接口中的四个方法：poll()、peek()、peekLast() 和 offer()。

1. poll() 方法用于检索并删除队列的头元素（首部元素）。如果队列为空，poll() 方法将返回 null。
2. peek() 方法用于检索队列的头元素（首部元素），但不删除它。如果队列为空，peek() 方法将返回 null。
3. peekLast() 方法用于检索队列的尾元素（尾部元素），但不删除它。如果队列为空，peekLast() 方法将返回 null。
4. offer() 方法用于在队列的尾部插入一个元素。如果队列已满，则 offer() 方法将返回 false，否则返回 true。

下面是这些方法的示例用法：

import java.util.*;
public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        
        // 添加元素到队列尾部
        deque.offer(1);
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque); // 输出: [1, 2, 3]
        
        // 检索并删除队列头部元素
        int first = deque.poll();
        System.out.println(first); // 输出: 1
        System.out.println(deque); // 输出: [2, 3]
        
        // 检索队列头部元素但不删除
        int peeked = deque.peek();
        System.out.println(peeked); // 输出: 2
        
        // 检索队列尾部元素但不删除
        int peekedLast = deque.peekLast();
        System.out.println(peekedLast); // 输出: 3
    }
}
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

总结：Deque 接口中的 poll()、peek()、peekLast() 和 offer() 方法分别用于检索和操作双端队列的元素。poll() 方法从队列头部检索并删除元素，peek() 方法从队列头部检索元素但不删除，peekLast() 方法从队列尾部检索元素但不删除，offer() 方法将元素插入到队列尾部。

END

说实话，还是很有难度的，那个滑动窗口和堆的配合我也是想了半天才搞懂，不就是力扣上的难度题目，我没事😎🤏🕶 -> 😭 。