239. 滑动窗口最大值#

用生活中的例子来理解#

想象你是一位摄影师，在拍摄一场马拉松比赛。你的相机一次只能拍摄3个跑步者（就像一个宽度为3的窗口）。随着比赛进行，你的镜头不断向前移动，每次只移动一点点，要在每张照片中找出最高的那位跑步者的身高。这就是我们今天要解决的”滑动窗口最大值”问题。

问题描述#

题目目标#

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

示例 1#

输入： nums = [1,3,-1,-3,5,3,6,7], k = 3 输出： [3,3,5,5,6,7] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

问题是什么#

LeetCode第239题“滑动窗口最大值”给我们一个任务：假设有一个数组，比如 [2,3,4,2,6,2,5,1]，然后给我们一个宽度为3的窗口。这个窗口会从左往右滑动，每次移动一格。我们需要记录下每个窗口中的最大值。

举个简单的例子：

数组：[2,3,4]  窗口大小：2

第一个窗口：[2,3] 4   最大值是3
第二个窗口：2 [3,4]   最大值是4

所以最终结果是：[3,4]

plaintext

最简单的解决方案：看一看比一比#

就像我们肉眼看照片找最高的人一样，最简单的方法就是每次都看窗口里的所有数字，找出最大的那个。

// 这是最容易理解的方法
public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];  // 结果数组长度 = 可形成的窗口个数

    // 枚举每个窗口的起点 i（窗口范围是 [i, i + k - 1]）
    for (int i = 0; i <= nums.length - k; i++) {
        int max = nums[i];  // 先假设窗口第一个元素是当前最大值

        // 遍历窗口剩余元素，持续更新最大值
        for (int j = 1; j < k; j++) {
            if (nums[i + j] > max) {
                max = nums[i + j]; // 如果发现更大的值，就替换当前最大值
            }
        }

        result[i] = max;  // 记录“以 i 为起点的窗口”的最大值
    }

    return result; // 返回所有窗口最大值
}

java

这个方法很直观，就像用眼睛一个一个数字比较。但是，如果数组很长，窗口很大，这样做就会很慢。

聪明的解决方案：排队游戏#

现在我们来学一个更聪明的方法。想象一个游戏：

我们有一群小朋友排队，每个小朋友手里举着一个数字牌。
我们要保证队伍里的小朋友，从前到后手里的数字是从大到小的。
当新的小朋友要进队时，就要把队伍后面所有比他数字小的小朋友请出队。
队伍最前面的小朋友，就是当前窗口的最大值。

用代码来实现这个想法：

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0) return new int[0]; // 边界处理：空数组直接返回空结果

    int[] result = new int[nums.length - k + 1];  // 存放每个窗口最大值
    Deque<Integer> queue = new LinkedList<>();     // 双端队列里存“下标”，并维持对应值单调递减

    for (int i = 0; i < nums.length; i++) {
        // 1) 移除队头中已经滑出窗口范围的下标
        // 当前窗口左边界是 i - k + 1，若队头下标 < 左边界，说明它已过期
        if (!queue.isEmpty() && queue.peek() < i - k + 1) {
            queue.poll(); // 队头过期，弹出
        }

        // 2) 维护单调递减队列：把队尾所有“小于当前值”的下标都移除
        // 因为它们不可能再成为后续窗口的最大值
        while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
            queue.pollLast(); // 队尾对应值更小，且更早进入窗口，价值被当前元素完全覆盖
        }

        queue.offer(i); // 3) 当前下标入队

        // 4) 当 i >= k - 1 时，窗口已形成，队头就是当前窗口最大值下标
        if (i >= k - 1) {
            result[i - k + 1] = nums[queue.peek()]; // 记录当前窗口最大值
        }
    }

    return result; // 返回所有窗口最大值
}

java

让我们用一个具体的例子来看这个过程：

数组：[3,1,4,2]  窗口大小：2

初始状态：队伍为空

1. 数字3来了：
   队伍：[3]

2. 数字1来了：
   因为1比3小，直接排在3后面
   队伍：[3,1]
   第一个窗口的最大值是3

3. 数字4来了：
   4比1大，1离开队伍
   4比3大，3离开队伍
   队伍：[4]
   第二个窗口的最大值是4

4. 数字2来了：
   2比4小，直接排在4后面
   队伍：[4,2]
   第三个窗口的最大值是4

plaintext

为什么这样做更好？#

每个数字最多只会进队一次，出队一次
我们不用每次都看窗口里的所有数字
队伍的最前面永远是当前窗口的最大值

这就像在拍马拉松照片时，不用每次都量所有人的身高，而是保持一个有序的记录，随时知道当前画面中最高的人是谁。

小结#

解决滑动窗口最大值问题，关键是要想到：

我们不需要记住窗口里的所有数
只需要保持一个”从大到小”的顺序
及时把不在窗口范围内的数字删除

这样，我们就把一个看起来很复杂的问题，变成了一个简单的”排队游戏”！