滑动窗口最大值

发表于 更新于 分类于

算法-滑动窗口最大值

背景

  • 算法–滑动窗口最大值

  • 博主以代码随想录算法公开课进行学习

题目

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

    返回滑动窗口中的最大值。

    进阶：

    你能在线性时间复杂度内解决此题吗？

思路

  • 核心逻辑：滑动窗口求最大值的核心是用「单调递减队列」维护窗口内的最大值候选： - 单调递减队列特性：队列中元素从队首到队尾依次递减，队首始终是当前窗口的最大值； - 核心优势：避免暴力遍历窗口（O(nk)），通过队列维护候选值，每个元素仅入队/出队一次，时间复杂度优化至O(n)。
  • 具体步骤：
    • 自定义单调队列（核心工具）：
      • poll(val)：移除窗口左侧滑出的元素——仅当该元素是队首（当前最大值）时，才从队首弹出；
      • add(val)：添加窗口右侧新元素——循环剔除队尾所有比当前val小的元素（这些元素不可能成为后续窗口的最大值），再将val加入队尾，保证队列单调递减；
      • peek()：获取当前窗口的最大值（队首元素）。
    • 滑动窗口执行流程：
      • 初始化：将前k个元素加入单调队列，记录第一个窗口的最大值；
      • 滑动遍历：从第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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 1){
            return nums;
        }
        // 结果数组长度 = 窗口数量
        int len = nums.length - k + 1;
        int[] res = new int[len];
        int num = 0;
        MyQueue myQueue = new MyQueue();
          // 第一步：初始化前k个元素到队列中
        for(int i = 0;i < k; i++){
            myQueue.add(nums[i]);
        }
         // 记录第一个窗口的最大值
          res[num++] = myQueue.peek();
           // 第二步：滑动窗口遍历（从第k个元素开始）
        for(int i = k;i < nums.length;i++){
                // 1. 移除窗口左侧滑出的元素（nums[i-k]是当前窗口要删掉的最左元素）
            myQueue.poll(nums[i-k]);
              // 2. 添加窗口右侧新进入的元素（nums[i]是当前窗口要加的最右元素）
            myQueue.add(nums[i]);
             // 3. 记录当前窗口的最大值
            res[num++] = myQueue.peek();
        }
        return res;
    }
    
}

class MyQueue{
     // 底层用LinkedList实现双端队列，存储的是数组的值（而非下标）
    Deque<Integer> deque = new LinkedList<>();
    // 方法1：弹出窗口左侧移除的元素（仅当该元素是队列的队首时才弹出）
    void poll(int val){
        // 只有当队列非空，且要移除的val正好是队首（当前最大值）时，才弹出队首
        // 若val不是队首，说明它早已被add方法剔除，无需处理
        if(!deque.isEmpty()&&val == deque.peek()){
            deque.poll();
        }
    }
       // 方法2：添加新元素到队列，维护单调递减性
    void add(int val){
        // 循环剔除队尾所有比当前val小的元素
        // 因为这些元素在val的右侧，不可能成为后续窗口的最大值
        while(!deque.isEmpty()&&val>deque.getLast()){
            deque.removeLast();
        }
            // 此时队尾元素 >= val，加入后队列仍保持单调递减
        deque.add(val);
    }
     // 方法3：获取当前队列的最大值（即队首元素）
    int peek(){
        return deque.peek();
    }
}

总结

  • 核心知识点:
    • 单调队列的核心价值：滑动窗口问题中，通过「维护候选值的单调性」避免重复计算，将时间复杂度从暴力法的 O (nk) 优化至 O (n)；
    • 单调递减队列的设计逻辑：
      • 队首：当前窗口的最大值；
      • 队中元素：后续窗口可能成为最大值的候选（按递减顺序排列）；
      • 剔除规则：新元素加入时，剔除所有比它小的队尾元素（这些元素无成为最大值的可能）
    • 边界处理：数组长度为 1 时直接返回原数组，避免数组越界。