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?
思路
- 维护一个双端队列，使队列中的值保持递减，即队首为最大值；
- 如果遍历到的值的index >=k-1，即已经滑动到一个窗口的大小，则把队首元素加入结果；
- 如果此时队列长度已经大于k，则把队首元素移除。
def maxSlidingWindow2(self,nums,k):
indices = deque()
result = []
for i in range(len(nums)):
while indices and nums[i]>nums[indices[-1]]:
indices.pop()
indices.append(i)
if i >= k-1:
result.append(nums[indices[0]])
if i-k+1 == indices[0]:
indices.popleft()
return result
另一种则为暴力法，直接遍历找最大。
def maxSlidingWindow(self, nums, k):
if not nums:
return nums
result = []
for i in range(len(nums)-k+1):
if i + k <= len(nums):
subList = nums[i:i+k]
result.append(max(subList))
else:
subList = nums[i:]
result.append(max(subList))
return result
