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.
解题方法
heap
如果用一个maxheap的话，那么删除数据的时候比较麻烦，所以需要用hashheap以达到快速找最大值和快速删除的效果
deque
用一个Deque, 前后都可以pop, 但是如果只是按顺序把element加入的话还需要求最大值，额外增加了复杂度。我们可以只存能够成为候选最大值 的element的index， 存index是方便删除的时候判断。
比如 [1,2,3,7,5,6], window size 4
1,2,3,7时，我们只需要在deque中存7的Index 3就可以，因为前面1，2，3在被删除时，并不会影响window max,也就不是最大值的候选，所以不用存。 所以方法的步骤就是：
- 遇到一个新的元素index为i，value为v, 将deque末尾小于它的value都pop掉，直到比它大的，然后将i加到Deque的末尾
- 如果size > k了,
if i - k == deque[0]: deque.popleft() deque[0]是当前window的最大值
Solution
from collections import deque
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []
if not k:
return nums
window = deque()
length = len(nums)
p = 0
result = []
while p < length:
while window and nums[window[-1]] < nums[p]:
window.pop()
window.append(p)
if p - k == window[0]:
window.popleft()
if p >= k - 1:
result.append(nums[window[0]])
p += 1
return result