FilesExpand file tree

 master

/

sliding_window_max.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

41 lines (37 loc) · 1.05 KB

 master

/

sliding_window_max.py

Copy path

Top

File metadata and controls

• Code
• Blame

41 lines (37 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

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.

For example,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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

Therefore, return the max sliding window as [3,3,5,5,6,7].

"""

import collections

def max_sliding_window(nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: List[int]

"""

if not nums:

return nums

queue = collections.deque()

res = []

for num in nums:

if len(queue) < k:

queue.append(num)

else:

res.append(max(queue))

queue.popleft()

queue.append(num)

res.append(max(queue))

return res