/
Sliding Window Maximum.py
95 lines (83 loc) · 2.38 KB
/
Sliding Window Maximum.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# https://leetcode.com/discuss/65240/python-simple-solution
class Solution(object):
def maxSlidingWindow(self, nums, k):
ans = []
queue = []
for i, v in enumerate(nums):
if queue and queue[0] <= i - k:
queue = queue[1:]
while queue and nums[queue[-1]] < v:
queue.pop()
queue.append(i)
if i + 1 >= k:
ans.append(nums[queue[0]])
return ans
class maxqueue(object):
def __init__(self):
self.queue = []
self.maxs = []
def push(self, x):
self.queue.append(x)
while self.maxs and self.maxs[-1] < x:
self.maxs.pop()
self.maxs.append(x)
def pop(self):
if self.queue[0] == self.maxs[0]:
self.maxs.pop(0)
self.queue.pop(0)
def mymax(self):
return self.maxs[0]
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []
res = []
q = maxqueue()
for i in range(k):
if i < len(nums):
q.push(nums[i])
res.append(q.mymax())
for i in range(k, len(nums)):
q.pop()
q.push(nums[i])
res.append(q.mymax())
return res
# TLE
import heapq
from collections import defaultdict
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []
if len(nums) <= k:
return [max(nums)]
dict = defaultdict(int)
queue = []
res = []
for i in range(k):
dict[nums[i]] += 1
heapq.heappush(queue, -nums[i])
# print -heapq.nsmallest(1, queue)[0]
res.append(-heapq.nsmallest(1, queue)[0])
for i in range(k, len(nums)):
dict[nums[i - k]] -= 1
dict[nums[i]] += 1
heapq.heappush(queue, -nums[i])
largest = -heapq.nsmallest(1, queue)[0]
while dict[largest] <= 0:
largest = -heapq.heappop(queue)
res.append(largest)
return res
if __name__ == "__main__":
a = Solution()
print a.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)