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?
思路
- 維護(hù)一個(gè)雙端隊(duì)列，使隊(duì)列中的值保持遞減察迟，即隊(duì)首為最大值；
- 如果遍歷到的值的index >=k-1，即已經(jīng)滑動(dòng)到一個(gè)窗口的大小，則把隊(duì)首元素加入結(jié)果瞒滴；
- 如果此時(shí)隊(duì)列長度已經(jīng)大于k迎瞧，則把隊(duì)首元素移除。
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
