239. 滑动窗口最大值

力扣题目链接 (opens new window)

题目描述

给定一个整数数组 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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

思路

最直接的办法是每移动一次窗口，就重新扫描窗口中的 k 个元素。这样需要 O(n × k) 的时间。当 n 和 k 都很大时，重复扫描太多了。

窗口右移一格，只会有一个元素离开、一个元素进入。能不能维护一份“最大值候选名单”，让答案随时都在最前面？

队列里存什么

用双端队列存元素下标。下标既能找到对应的数值，也能判断元素是否已经离开窗口。

从队首到队尾，下标对应的数值保持单调递减。队首就是当前窗口最大值的下标。队列不需要存下窗口中的所有元素。

为什么可以丢掉一部分元素？如果新进入的数比队尾的数大，那么队尾元素更小、位置还更靠左，会比新元素更早离开窗口。只要新元素还在窗口里，旧元素就不可能成为最大值。 所以可以从队尾删除它。

相等的数也可以删除旧下标，留下更靠右的新下标：它能在窗口中待得更久。这样队列中的数值严格递减。

窗口移动时做什么

遍历到下标 i 时，当前窗口左边界是 i - k + 1：

1. 如果队首下标 <= i - k，它已经离开窗口，从队首弹出。
2. 从队尾弹出所有 nums[队尾下标] <= nums[i] 的下标。
3. 将 i 加入队尾。
4. 当 i >= k - 1 时，窗口已经形成，记录 nums[队首下标]。

队首处理的是“过期”，队尾处理的是“更大的新元素淘汰旧候选”。 这两个方向别写反了。

模拟过程

以 nums = [1,3,-1,-3,5,3,6,7]，k = 3 为例。下面的队列写作 下标:数值，从左到右分别是队首和队尾。

先形成第一个窗口 [1,3,-1]。读到 3 时，1 从队尾被淘汰；读到 -1 后，队列为 [1:3, 2:-1]，记录第一个最大值 3。

读到下标 3 的 -3，队列变为 [1:3, 2:-1, 3:-3]，第二个窗口的最大值仍是 3。继续读到下标 4 时，窗口变为 [-1,-3,5]，下标 1 已经过期，先从队首移出。

然后 5 从队尾依次淘汰 -3、-1，加入下标 4。此时队列只剩 [4:5]，第三个窗口的最大值是 5。

后面的窗口按同样规则处理：

窗口下标	窗口元素	处理后的队列	最大值
[0,2]	[1,3,-1]	[1:3, 2:-1]	3
[1,3]	[3,-1,-3]	[1:3, 2:-1, 3:-3]	3
[2,4]	[-1,-3,5]	[4:5]	5
[3,5]	[-3,5,3]	[4:5, 5:3]	5
[4,6]	[5,3,6]	[6:6]	6
[5,7]	[3,6,7]	[7:7]	7

很多录友会担心重复最大值。比如窗口中有两个 3，后来的 3 会淘汰先前的 3，但后来的下标更靠右，至少能覆盖旧下标还在窗口的所有后续窗口，所以答案不会丢。

解题代码

C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> que; // 保存下标，队首对应当前最大值
        vector<int> result;

        for (int i = 0; i < nums.size(); i++) {
            // 队首如果已经离开窗口，就不能再参与答案
            if (!que.empty() && que.front() <= i - k) que.pop_front();

            // 新元素更靠右且不小于队尾元素，旧元素不可能再成为最大值
            while (!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
            que.push_back(i);

            if (i >= k - 1) result.push_back(nums[que.front()]);
        }

        return result;
    }
};

复杂度分析

• 时间复杂度：O(n)。每个下标最多入队一次、从队首或队尾出队一次。
• 空间复杂度：O(k)。队列只保存当前窗口内的下标；结果数组不计入辅助空间。

其他语言

Python3

from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = deque()
        result = []

        for i, num in enumerate(nums):
            if que and que[0] <= i - k:
                que.popleft()

            while que and nums[que[-1]] <= num:
                que.pop()
            que.append(i)

            if i >= k - 1:
                result.append(nums[que[0]])

        return result

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            if (!que.isEmpty() && que.peekFirst() <= i - k) {
                que.pollFirst();
            }

            while (!que.isEmpty() && nums[que.peekLast()] <= nums[i]) {
                que.pollLast();
            }
            que.offerLast(i);

            if (i >= k - 1) {
                result[i - k + 1] = nums[que.peekFirst()];
            }
        }

        return result;
    }
}

Go

import "container/list"

func maxSlidingWindow(nums []int, k int) []int {
    result := make([]int, 0, len(nums)-k+1)
    que := list.New() // 队列中存下标

    for i, num := range nums {
        if que.Len() > 0 && que.Front().Value.(int) <= i-k {
            que.Remove(que.Front())
        }

        for que.Len() > 0 && nums[que.Back().Value.(int)] <= num {
            que.Remove(que.Back())
        }
        que.PushBack(i)

        if i >= k-1 {
            result = append(result, nums[que.Front().Value.(int)])
        }
    }

    return result
}

JS

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const que = new Int32Array(k); // 固定容量的环形双端队列，存下标
    const result = [];
    let head = 0;
    let size = 0;

    for (let i = 0; i < nums.length; i++) {
        if (size > 0 && que[head] <= i - k) {
            head = (head + 1) % k;
            size--;
        }

        while (size > 0 && nums[que[(head + size - 1) % k]] <= nums[i]) {
            size--;
        }
        que[(head + size) % k] = i;
        size++;

        if (i >= k - 1) result.push(nums[que[head]]);
    }

    return result;
};

与代码随想录联系

我在代码随想录的239. 滑动窗口最大值中，详细讲过单调队列的 push、pop 如何配合窗口移动。这里改用下标来实现：过期判断直接比较窗口左边界，重复数值也能清楚地区分谁先离开。

这道题可以接着 438. 找到字符串中所有字母异位词 学。两题都是定长窗口；438 题维护窗口内字符的频次，本题维护窗口内仍可能成为最大值的候选下标。如果还不熟悉双端队列，可以先看栈与队列基础。