# Python o(n) time 180ms

• ``````class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []

local_m = nums[0]
local_p = 0
res =[]
for i in range(1,k): #find the max value of the first k numbers

if nums[i] >= local_m:
local_m, local_p = nums[i], i
res.append(local_m)

for i in range(k, len(nums)):
start_p = i - k+1
if local_p >= start_p:   # if the previously saved max position is in the window, and current #number smaller than the maxvalue, store the number
if local_m > nums[i]:
res.append(local_m)
elif local_m <= nums[i]:
local_p = i
local_m = nums[i]
res.append(local_m)
else:  #Otherwise, search the new max_val and max position in the current windows.
local_m = nums[i]
local_p = i
for j in range(start_p, i):
if nums[j] >= local_m:
local_m, local_p = nums[j], j
res.append(local_m)

return res``````

• I think the worstcase is O(kn), right?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.