[LeetCode]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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 

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

Follow up:

Could you solve it in linear time?

Hint:

How about using a data structure such as deque (double-ended queue)?

The queue size need not be the same as the window’s size.

Remove redundant elements and the queue should store only elements that need to be considered.

题目大意:

给定一个数组,一个大小为k的滑动窗口从数组的最左端向最右端移动。你只可以看到窗口中的k个数字。每一次窗口向右边移动一步。

例如,给定数组nums = [1,3,-1,-3,5,3,6,7], k = 3

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

因此,返回滑动窗口最大值是[3,3,5,5,6,7]

注意:

你可以假设k总是有效的,也就是说:1 ≤ k ≤ 输入数组的大小,并且数组非空。

进一步思考:

你可以在线性时间内完成吗?

提示:

使用数据结构deque(双端队列)如何?

队列的大小不一定和窗口的大小相同。

从队列中移除冗余元素,并且只存储需要被考虑的元素。

解题思路:

参考LeetCode Discuss:https://leetcode.com/discuss/46578/java-o-n-solution-using-deque-with-explanation

遍历数组nums,使用双端队列deque维护滑动窗口内有可能成为最大值元素的数组下标

由于数组中的每一个元素至多只会入队、出队一次,因此均摊时间复杂度为O(n)

记当前下标为i,则滑动窗口的有效下标范围为[i - (k - 1), i]

若deque中的元素下标< i - (k - 1),则将其从队头弹出,deque中的元素按照下标递增顺序从队尾入队。

这样就确保deque中的数组下标范围为[i - (k - 1), i],满足滑动窗口的要求。

当下标i从队尾入队时,顺次弹出队列尾部不大于nums[i]的数组下标(这些被弹出的元素由于新元素的加入而变得没有意义)

deque的队头元素即为当前滑动窗口的最大值

Python代码:

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer[]}
    def maxSlidingWindow(self, nums, k):
        dq = collections.deque()
        ans = []
        for i in range(len(nums)):
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()
            dq.append(i)
            if dq[0] == i - k:
                dq.popleft()
            if i >= k - 1:
                ans.append(nums[dq[0]])
        return ans

 

本文链接:http://bookshadow.com/weblog/2015/07/18/leetcode-sliding-window-maximum/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码