문제
You are given an array of integers 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 1:
Input: nums = [1,3,-1,-3,5,3,6,7], 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
시간복잡도 생각 안 하고 무작정 작성했더니 시간 초과 떴다.
class Solution(object):
def maxSlidingWindow(self, nums, k):
output = []
for i in range(len(nums)-(k-1)):
output.append(max(nums[i:i+k]))
return output그래서 덱을 이용해서 다시 작성했는데 여기서 더 개선시키는 방법은 아직 모르겠다.
from collections import deque
class Solution(object):
def maxSlidingWindow(self, nums, k):
output = []
dq = deque()
for i in range(len(nums)):
if dq and dq[0] < i-k+1:
dq.popleft()
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k-1:
output.append(nums[dq[0]])
return output
```