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?
My code:
import numpy as np
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if len(nums)==0:
return []
if len(nums)<=k:
return [max(nums)]
if k==1:
return nums
max_tmp=nums[0]
max_index=0
start=0
result=[]
while start+k<len(nums)+1:
if start==0:
for kk in range(k):
if nums[start+kk]>max_tmp:
max_tmp=nums[start+kk]
max_index=start+kk
#max_tmp=max(nums[:k])
#max_index=np.argwhere(nums[:k]==max_tmp)
#print(max_index)
#if type(max_index)!=int:
#max_index=max_index[0]
else:
if nums[start+k-1]>max_tmp:
max_tmp=nums[start+k-1]
max_index=start+k-1
if start>max_index:
max_tmp=nums[start]
for kk in range(k):
if nums[start+kk]>max_tmp:
max_tmp=nums[start+kk]
max_index=start+kk
result.append(max_tmp)
start+=1
return result
Solution: https://leetcode.com/problems/sliding-window-maximum/