sliding_window_maximum

View Source

 1from collections import deque
 2
 3
 4# @leet start
 5class Solution:
 6    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
 7        """
 8        This question asks us to find the sliding window maximum. We could
 9        do this by having a deque of length `k` and calculating the max of
10        it as we pop and add to the queue. This, however, takes $O(n*k)$ time,
11        and thus times out.
12
13        We want to do this in $O(n)$ time, which is doable, as long as we use
14        a monotonically decreasing deque. So, we first check the last item
15        in the queue to make sure that it's smaller than the number we're
16        currently looking at. If not, we pop it in a while loop.
17
18        At the end, we append our right hand side to it.
19
20        We then check the left hand side, if our current left pointer has
21        a value greater than the first item in the queue, we pop it.
22
23        Finally, if our queue length is the size of the window, we add the
24        first item of the queue to the output array, since it is the largest
25        item in the window, and increment our left pointer.
26
27        At the end of the iteration, we increment our right pointer.
28        """
29        output = []
30        q = deque()
31        l = r = 0
32
33        while r < len(nums):
34            while q and nums[q[-1]] < nums[r]:
35                q.pop()
36            q.append(r)
37
38            if l > q[0]:
39                q.popleft()
40
41            if r + 1 >= k:
42                output.append(nums[q[0]])
43                l += 1
44            r += 1
45        return output
46
47
48# @leet end
49
50
51def test():
52    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
 8        """
 9        This question asks us to find the sliding window maximum. We could
10        do this by having a deque of length `k` and calculating the max of
11        it as we pop and add to the queue. This, however, takes $O(n*k)$ time,
12        and thus times out.
13
14        We want to do this in $O(n)$ time, which is doable, as long as we use
15        a monotonically decreasing deque. So, we first check the last item
16        in the queue to make sure that it's smaller than the number we're
17        currently looking at. If not, we pop it in a while loop.
18
19        At the end, we append our right hand side to it.
20
21        We then check the left hand side, if our current left pointer has
22        a value greater than the first item in the queue, we pop it.
23
24        Finally, if our queue length is the size of the window, we add the
25        first item of the queue to the output array, since it is the largest
26        item in the window, and increment our left pointer.
27
28        At the end of the iteration, we increment our right pointer.
29        """
30        output = []
31        q = deque()
32        l = r = 0
33
34        while r < len(nums):
35            while q and nums[q[-1]] < nums[r]:
36                q.pop()
37            q.append(r)
38
39            if l > q[0]:
40                q.popleft()
41
42            if r + 1 >= k:
43                output.append(nums[q[0]])
44                l += 1
45            r += 1
46        return output

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

 7    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
 8        """
 9        This question asks us to find the sliding window maximum. We could
10        do this by having a deque of length `k` and calculating the max of
11        it as we pop and add to the queue. This, however, takes $O(n*k)$ time,
12        and thus times out.
13
14        We want to do this in $O(n)$ time, which is doable, as long as we use
15        a monotonically decreasing deque. So, we first check the last item
16        in the queue to make sure that it's smaller than the number we're
17        currently looking at. If not, we pop it in a while loop.
18
19        At the end, we append our right hand side to it.
20
21        We then check the left hand side, if our current left pointer has
22        a value greater than the first item in the queue, we pop it.
23
24        Finally, if our queue length is the size of the window, we add the
25        first item of the queue to the output array, since it is the largest
26        item in the window, and increment our left pointer.
27
28        At the end of the iteration, we increment our right pointer.
29        """
30        output = []
31        q = deque()
32        l = r = 0
33
34        while r < len(nums):
35            while q and nums[q[-1]] < nums[r]:
36                q.pop()
37            q.append(r)
38
39            if l > q[0]:
40                q.popleft()
41
42            if r + 1 >= k:
43                output.append(nums[q[0]])
44                l += 1
45            r += 1
46        return output

This question asks us to find the sliding window maximum. We could do this by having a deque of length k and calculating the max of it as we pop and add to the queue. This, however, takes $O(n*k)$ time, and thus times out.

We want to do this in $O(n)$ time, which is doable, as long as we use a monotonically decreasing deque. So, we first check the last item in the queue to make sure that it's smaller than the number we're currently looking at. If not, we pop it in a while loop.

At the end, we append our right hand side to it.

We then check the left hand side, if our current left pointer has a value greater than the first item in the queue, we pop it.

Finally, if our queue length is the size of the window, we add the first item of the queue to the output array, since it is the largest item in the window, and increment our left pointer.

At the end of the iteration, we increment our right pointer.

def test(): View Source

52def test():
53    assert 2 + 2 == 4