leetcode/algorithms/sliding-window-maximum.py at master · sreejeet/leetcode · GitHub

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
class Solution:

    def maxSlidingWindow(self, nums: [int], k: int) -> [int]:

        l, r = 0, k
        max_r = len(nums)
        ans = [max(nums[l:r])]

        while r < max_r:

            r+=1
            l+=1

            # If the new number is larger than the last largest number,
            # we have the new largest number.
            if nums[r-1] > ans[-1]:
                ans.append(nums[r-1])

            # If we have lost the largest number,
            # find new largest number.
            elif nums[l-1] == ans[-1]:
                ans.append(max(nums[l:r]))

            # If neither cases match, repeat the last max.
            else:
                ans.append(ans[-1])

        return ans


if __name__=='__main__':

    sol = Solution()
    print(sol.maxSlidingWindow([1,-1], 1))

"""
[1,3,-1,-3,5,3,6,7]
3
[1,3,-1,-3,5,3,6,7]
1
[1,3,-1,-3,5,3,6,7]
8
[1,3,-1,-3,5,3,6,7]
7
[1,-1]
1
"""