法算day11

[up主专用，视频内嵌代码贴在这]

滑动窗口最大值

问题描述

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    滑动窗口的位置                最大值
    ---------------               -----
    [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

  • 示例 2：
    输入：nums = [1], k = 1
    输出：[1]

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

核心思路

这个算法使用双端队列（Deque）来高效地找到每个滑动窗口的最大值：

  1. 队列中存储的是数组元素的索引，而不是元素值本身
  2. 队列中的索引对应的元素值是递减的
  3. 队列头部始终是当前窗口的最大值的索引

语法解析

Deque<Integer> deque = new LinkedList<>();

  • Deque: 接口类型声明，表示这是一个双端队列，存储整数类型
  • deque: 变量名
  • new LinkedList<>(): 创建LinkedList类的实例作为Deque的实现
  • : 泛型，指定队列中存储的元素类型为整数

实际内存结构

  • 在内存中，LinkedList 实现的Deque大致如下：
    1
    2
    3
    deque → [头节点] ↔ [节点1] ↔ [节点2] ↔ ... ↔ [尾节点]
              ↓          ↓          ↓               ↓
              索引        索引       索引           索引

Deque的常用方法

  • 队首操作
    1
    2
    3
    4
    5
    6
    deque.addFirst(element);    // 在队首添加元素
    deque.offerFirst(element);  // 在队首添加元素（推荐）
    deque.removeFirst();        // 移除并返回队首元素
    deque.pollFirst();          // 移除并返回队首元素（推荐）
    deque.getFirst();           // 获取队首元素（不移除）
    deque.peekFirst();          // 获取队首元素（不移除，推荐）
  • 队尾操作
    1
    2
    3
    4
    5
    6
    deque.addLast(element);     // 在队尾添加元素
    deque.offerLast(element);   // 在队尾添加元素（推荐）
    deque.removeLast();         // 移除并返回队尾元素
    deque.pollLast();           // 移除并返回队尾元素（推荐）
    deque.getLast();            // 获取队尾元素（不移除）
    deque.peekLast();           // 获取队尾元素（不移除，推荐）

java版

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 如果数组为空或k为0，直接返回空数组
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        
        // 结果数组的长度是 nums.length - k + 1
        int[] result = new int[nums.length - k + 1];
        // 使用双端队列来存储索引，队列中的索引对应的值是递减的
        Deque<Integer> deque = new LinkedList<>();
        
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 移除队列中不在当前窗口范围内的索引
            // 窗口范围是 [i-k+1, i]，所以索引小于 i-k+1 的元素都不在窗口内
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst(); // 从队首移除
            }
            
            // 移除队列中所有小于当前元素的索引
            // 因为这些元素不可能是当前窗口或未来窗口的最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast(); // 从队尾移除
            }
            
            // 将当前元素的索引添加到队列尾部
            deque.offerLast(i);
            
            // 当窗口形成时（即i >= k-1），将当前窗口的最大值添加到结果数组中
            // 当前窗口的最大值就是队列头部的索引对应的元素
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
    
    // 测试代码
    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();
        
        // 示例1
        int[] nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
        int k1 = 3;
        int[] result1 = solution.maxSlidingWindow(nums1, k1);
        System.out.println("输入: nums = [1,3,-1,-3,5,3,6,7], k = 3");
        System.out.print("输出: ");
        System.out.println(Arrays.toString(result1)); // 输出: [3,3,5,5,6,7]
        
        // 示例2
        int[] nums2 = {1};
        int k2 = 1;
        int[] result2 = solution.maxSlidingWindow(nums2, k2);
        System.out.println("输入: nums = [1], k = 1");
        System.out.print("输出: ");
        System.out.println(Arrays.toString(result2)); // 输出: [1]
        
        // 额外测试用例
        int[] nums3 = {1, -1};
        int k3 = 1;
        int[] result3 = solution.maxSlidingWindow(nums3, k3);
        System.out.println("输入: nums = [1,-1], k = 1");
        System.out.print("输出: ");
        System.out.println(Arrays.toString(result3)); // 输出: [1,-1]
    }
}

✅ 说明：

  • 时间复杂度O(n)
  • 空间复杂度O(k)

滑动窗口移除逻辑详细示例说明nums1 = {1, 3, -1, -3, 5, 3, 6, 7};k1 = 3;

  • 初始状态

    1
    2
    队列 dq: [] (空)
    结果 result: []

  • 步骤1: i=0, nums[0]=1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    当前元素: 1
    窗口: [1] (大小不足k，不记录结果)

    操作:
    1. 队列为空，直接添加索引0
    2. dq = [0] → 对应值 [1]

    解释:
    - 队列中只有一个元素，所以它自然是当前窗口的最大值
    - 但窗口大小不足k，所以不记录结果

  • 步骤2: i=1, nums[1]=3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 3
    窗口: [1, 3] (大小不足k，不记录结果)

    操作:
    1. 检查队首索引0是否在窗口内: 0 <= 1-3? 0 <= -2? 否，保留
    2. 从队尾开始比较: nums[0]=1 < 3，移除索引0
    3. 添加索引1
    4. dq = [1] → 对应值 [3]

    解释:
    - 3比1大，所以移除1，队列中只保留3
    - 当前窗口[1,3]的最大值是3
    - 但窗口大小不足k，不记录结果

  • 步骤3: i=2, nums[2]=-1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    当前元素: -1
    窗口: [1, 3, -1] (大小达到k，记录结果)

    操作:
    1. 检查队首索引1是否在窗口内: 1 <= 2-3? 1 <= -1? 否，保留
    2. 从队尾开始比较: nums[1]=3 > -1，不移除，直接添加索引2
    3. dq = [1, 2] → 对应值 [3, -1]
    4. 记录结果: nums[1] = 3
    5. result = [3]

    解释:
    - 3比-1大，所以保留3在队首，-1添加到队尾
    - 队列保持递减: [3, -1]
    - 当前窗口[1,3,-1]的最大值是3，由队首元素提供

  • 步骤4: i=3, nums[3]=-3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    当前元素: -3
    窗口: [3, -1, -3] (大小达到k，记录结果)

    操作:
    1. 检查队首索引1是否在窗口内: 1 <= 3-3? 1 <= 0? 否，保留
    2. 从队尾开始比较: nums[2]=-1 > -3，不移除，直接添加索引3
    3. dq = [1, 2, 3] → 对应值 [3, -1, -3]
    4. 记录结果: nums[1] = 3
    5. result = [3, 3]

    解释:
    - -3比-1小，所以直接添加到队尾
    - 队列保持递减: [3, -1, -3]
    - 当前窗口[3,-1,-3]的最大值是3，由队首元素提供

  • 步骤5: i=4, nums[4]=5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    当前元素: 5
    窗口: [-1, -3, 5] (大小达到k，记录结果)

    操作:
    1. 检查队首索引1是否在窗口内: 1 <= 4-3? 1 <= 1? 是，移除索引1
       - 现在 dq = [2, 3] → 对应值 [-1, -3]
    2. 从队尾开始比较: nums[3]=-3 < 5，移除索引3
       - 现在 dq = [2] → 对应值 [-1]
    3. 继续比较: nums[2]=-1 < 5，移除索引2
       - 现在 dq = [] (空)
    4. 添加索引4
    5. dq = [4] → 对应值 [5]
    6. 记录结果: nums[4] = 5
    7. result = [3, 3, 5]

    解释:
    - 首先移除不在窗口内的索引1(对应值3)
    - 然后移除所有比5小的元素(-1和-3)
    - 队列中只剩下5
    - 当前窗口[-1,-3,5]的最大值是5，由队首元素提供

  • 步骤6: i=5, nums[5]=3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    当前元素: 3
    窗口: [-3, 5, 3] (大小达到k，记录结果)

    操作:
    1. 检查队首索引4是否在窗口内: 4 <= 5-3? 4 <= 2? 否，保留
    2. 从队尾开始比较: nums[4]=5 > 3，不移除，直接添加索引5
    3. dq = [4, 5] → 对应值 [5, 3]
    4. 记录结果: nums[4] = 5
    5. result = [3, 3, 5, 5]

    解释:
    - 5比3大，所以保留5在队首，3添加到队尾
    - 队列保持递减: [5, 3]
    - 当前窗口[-3,5,3]的最大值是5，由队首元素提供

  • 步骤7: i=6, nums[6]=6

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    当前元素: 6
    窗口: [5, 3, 6] (大小达到k，记录结果)

    操作:
    1. 检查队首索引4是否在窗口内: 4 <= 6-3? 4 <= 3? 否，保留
    2. 从队尾开始比较: nums[5]=3 < 6，移除索引5
       - 现在 dq = [4] → 对应值 [5]
    3. 继续比较: nums[4]=5 < 6，移除索引4
       - 现在 dq = [] (空)
    4. 添加索引6
    5. dq = [6] → 对应值 [6]
    6. 记录结果: nums[6] = 6
    7. result = [3, 3, 5, 5, 6]

    解释:
    - 移除所有比6小的元素(5和3)
    - 队列中只剩下6
    - 当前窗口[5,3,6]的最大值是6，由队首元素提供

  • 步骤8: i=7, nums[7]=7

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    当前元素: 7
    窗口: [3, 6, 7] (大小达到k，记录结果)

    操作:
    1. 检查队首索引6是否在窗口内: 6 <= 7-3? 6 <= 4? 否，保留
    2. 从队尾开始比较: nums[6]=6 < 7，移除索引6
       - 现在 dq = [] (空)
    3. 添加索引7
    4. dq = [7] → 对应值 [7]
    5. 记录结果: nums[7] = 7
    6. result = [3, 3, 5, 5, 6, 7]

    解释:
    - 移除所有比7小的元素(6)
    - 队列中只剩下7
    - 当前窗口[3,6,7]的最大值是7，由队首元素提供

为什么队首总是最大值？

通过这个详细示例，我们可以看到：

  • 队列始终保持递减：从队首到队尾，元素值逐渐减小
  • 队首元素总是在窗口内：我们定期检查并移除不在窗口内的元素
  • 没有更大的元素被遗漏：
    如果有更大的元素，它会在加入队列时移除所有比它小的元素
    然后它自己成为新的队首
    因此，在每一步中，队首元素都代表了当前窗口中的最大值。
    这个算法的巧妙之处在于，它通过维护一个单调递减队列，使得我们可以在O(1)时间内获取当前窗口的最大值，而维护队列的均摊时间复杂度也是O(1)，整体算法时间复杂度为O(n)。

python版

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
57
58
59
60
61
from collections import deque

def maxSlidingWindow(nums, k):
    """
    使用双端队列找到滑动窗口的最大值
    
    参数:
        nums: 整数数组
        k: 滑动窗口的大小
    
    返回:
        一个列表，包含每个滑动窗口的最大值
    """
    # 存储结果的最大值
    result = []
    # 使用双端队列，存储数组元素的索引
    # 队列中的索引对应的元素值是递减的（队首元素最大）
    dq = deque()
    
    # 遍历数组中的每个元素
    for i in range(len(nums)):
        # 移除队列中已经不在当前窗口的索引
        # 如果队首索引小于等于i-k，说明它不在当前窗口内，需要移除
        if dq and dq[0] <= i - k:
            dq.popleft()  # 从队首移除
        
        # 从队尾开始，移除所有小于当前元素的索引
        # 因为这些元素不可能成为当前或未来窗口的最大值
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()  # 从队尾移除
        
        # 将当前元素的索引加入队尾
        dq.append(i)
        
        # 当窗口大小达到k时，开始记录结果
        # i从0开始，所以当i >= k-1时，窗口大小达到k
        if i >= k - 1:
            # 队首元素就是当前窗口的最大值
            result.append(nums[dq[0]])
    
    return result

# 测试代码
if __name__ == "__main__":
    # 示例1
    nums1 = [1, 3, -1, -3, 5, 3, 6, 7]
    k1 = 3
    print(f"输入: nums = {nums1}, k = {k1}")
    print(f"输出: {maxSlidingWindow(nums1, k1)}")  # 输出: [3, 3, 5, 5, 6, 7]
    
    # 示例2
    nums2 = [1]
    k2 = 1
    print(f"输入: nums = {nums2}, k = {k2}")
    print(f"输出: {maxSlidingWindow(nums2, k2)}")  # 输出: [1]
    
    # 额外测试用例
    nums3 = [7, 2, 4]
    k3 = 2
    print(f"输入: nums = {nums3}, k = {k3}")
    print(f"输出: {maxSlidingWindow(nums3, k3)}")  # 输出: [7, 4]