每日算法系列【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

提示
你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

题解

双端单调队列

本题要找长度为 k 的区间的最大值。模拟这个区间的移动过程,可以发现,右边增加一个数,左边必然会去掉一个数。

那么最大的数有什么性质呢?可以发现,如果扫描区间末尾,在已经遍历过的数之中,一个数 a 在 b 前面,并且 a 还比 b 小,那么 a 在之后的区间里永远无法成为最大值。

所以我们遍历到一个数时,它之前的所有比它小的数都可以去掉了,只保留比它大的数就行了。这就让人想到了之前介绍过的单调栈,但是本题中是先进先出,所以要改用单调队列。此外队列末尾不仅要增加元素,还得维护单调递减,适当去除一些元素,所以队列两端都得有插入和删除的功能。所以本题要使用双端队列,而队列中的元素又是单调递减的,所以又是双端单调队列。

这样思路就很明确了:

  • 遍历元素 nums[i] ,然后跟队列尾部元素比较,如果比尾部元素大,就出队,然后继续比较,直到 nums[i] 小于尾部元素,然后将它入队。
  • 然后用一下队列首部元素的下标,计算出队列中区间的长度,如果大于 k 了,那么队首元素就要出队。
  • 最后队首元素就是当前区间的最大值。

分块法

试想如果我们将数组划分为相同大小的若干块,每一块中最大值都是知道的话,那么要求区间最大值,只需要看它在哪几块里就行了。

那么块的大小应该设成多少呢?

如果块大小为 k ,就可以发现长度为 k 的区间 [i, j] 要么正好就是一个完整的块,要么跨越了两个相邻块。那么我们只需要知道 i 到它那块末尾元素中最大值,以及 j 到它那块开头最大值就行了,两个部分合并求最大值就是区间的最大值了。而每个元素到它自己那块的开头和末尾的最大值都可以预处理出来,方法和求前缀和类似。

那为什么块大小不能是其他值呢?如果块大小大于 k ,那么会出现区间完全包含于一块之中的情况,那就和不分块一样了。如果块大小小于 k ,那么就会出现区间横跨了好几块,那么还得遍历中间块的最大值。极端情况下如果块大小为 1 ,那么就等于暴力求解。

代码

双端单调队列(c++)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> Q;
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            while (!Q.empty() && nums[i] >= nums[Q.back()]) Q.pop_back();
            Q.push_back(i);
            if (i - Q.front() + 1 > k) Q.pop_front();
            if (i >= k-1) res.push_back(nums[Q.front()]);
        }
        return res;
    }
};

双端单调队列+数组实现(c++)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> Q(n, 0);
        vector<int> res;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            while (r-l > 0 && nums[i] >= nums[Q[r-1]]) r--;
            Q[r++] = i;
            if (i - Q[l] + 1 > k) l++;
            if (i >= k-1) res.push_back(nums[Q[l]]);
        }
        return res;
    }
};

分块法(c++)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> lmax(n, 0), rmax(n, 0);
        vector<int> res;
        if (!n) return res;
        for (int i = 0; i < n; ++i) {
            if (i%k == 0) lmax[i] = nums[i];
            else lmax[i] = max(lmax[i-1], nums[i]);
        }
        for (int i = n-1; i >= 0; --i) {
            if ((i+1)%k == 0 || i == n-1) rmax[i] = nums[i];
            else rmax[i] = max(rmax[i+1], nums[i]);
        }
        for (int i = k-1; i < n; ++i) {
            res.push_back(max(lmax[i], rmax[i-k+1]));
        }
        return res;
    }
};

双端单调队列(python)

import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        Q = collections.deque()
        res = []
        for i in range(n):
            while len(Q) > 0 and nums[i] >= nums[Q[-1]]:
                Q.pop()
            Q.append(i)
            if i - Q[0] + 1 > k:
                Q.popleft()
            if i >= k-1:
                res.append(nums[Q[0]])
        return res

双端单调队列+数组实现(python)

import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        Q = [0] * n
        res = []
        l, r = 0, 0
        for i in range(n):
            while r-l > 0 and nums[i] >= nums[Q[r-1]]:
                r -= 1
            Q[r] = i
            r += 1
            if i - Q[l] + 1 > k:
                l += 1 
            if i >= k-1:
                res.append(nums[Q[l]])
        return res

分块法(python)

import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        lmax, rmax = [0] * n, [0] * n
        res = []
        if n == 0:
            return res
        for i in range(n):
            if i%k == 0:
                lmax[i] = nums[i]
            else:
                lmax[i] = max(lmax[i-1], nums[i])
        for i in range(n-1, -1, -1):
            if (i+1)%k == 0 or i == n-1:
                rmax[i] = nums[i]
            else:
                rmax[i] = max(rmax[i+1], nums[i])
        for i in range(k-1, n):
            res.append(max(lmax[i], rmax[i-k+1]))
        return res

后记

双端队列在 c++ 和 python 中都有 deque 的实现,如果你不会用的话,也可以用一个数组自己模拟一下,我觉得反而更加方便一点。


   转载规则


《每日算法系列【LeetCode 239】滑动窗口最大值》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
每日算法系列【LeetCode 115】不同的子序列 每日算法系列【LeetCode 115】不同的子序列
关注公众号【算法码上来】,每日算法干货马上就来! 题目描述给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。 一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字
2020-02-01
下一篇 
每日算法系列【LeetCode 312】戳气球 每日算法系列【LeetCode 312】戳气球
关注公众号【算法码上来】,每日算法干货马上就来! 题目描述有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[l
2020-01-30
  目录