[Leetcode 239] Sliding Window Maximum

原题说明

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

解题思路

这是一道比较好的面试题, 因为用priority queue的方法是容易想到的, 但是在实现的过程中也需要考虑一些边界条件, 比如刚开始扫的时候队列中少于k个数怎么处理, 什么时候结束等等. 这样方便面试官考察基本的coding能力.

对于followup, 相对来说要难一些, 用了双向队列(deque)结构来存储当前sliding window, 类似的问题有[LeetCode 316] Remove Duplicate Letters 移除重复字母
, [Leetcode 739] Daily Temperatures. 如果面试中能够想到的话, 就很接近Strong Hire了.

为了方便更新sliding window以及取出当前最大元素, 我们用的数据结构是deque. deque存储的是nums中对应元素的index. 主要思路是使得deque中的元素由老到新, 由大到小排列, 并且只存储之后可能会成为最大值的元素. 具体的方法是: 首先将超出窗口范围的老元素从队列头移出, 每次新扫到的元素与队列尾元素比较, 如果新的元素大, 则pop当前队尾元素(因为被pop的元素在窗口内必然小于新元素, 所以之后任意一步都不会成为最大值), 不然则直接插入新元素. 这样每走一步, 当前的deque头元素即为窗口中的最大值.

示例代码 (cpp)

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

示例代码 (python)

class Solution(object):         
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ret = []
        queue = collections.deque()
        for i in range(len(nums)):
            while(len(queue) and (queue[0] <= i - k)):
                queue.popleft()
            while(len(queue) and (nums[queue[-1]] < nums[i])):
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                ret.append(nums[queue[0]])
        return ret

复杂度分析

时间复杂度: O(n) 其中n为nums长度
空间复杂度: O(k)

归纳总结

同学们可以将解题思路中总结的类似题目一起做一遍, 这样对于处理这类问题会有更好的理解.