Monotonic queue

https://leetcode.com/problems/sliding-window-maximum/

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        d, res = collections.deque(), []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d.append(i)
            if d[0] == i - k:d.popleft()
            if i >= k - 1:
                res.append(nums[d[0]])
        return res

Some similar problems

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/largest-rectangle-in-histogram/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/