Leetcode List : https://leetcode.com/list/9rt1jt27

Monotonic Queue

The following question can be solved by monotonic queue:

• [ ] LC84. Largest Rectangle in Histogram
• [ ] LC239. Sliding Window Maximum
• [ ] LC739. Daily Temperatures
• [ ] LC862. Shortest Subarray with Sum at Least K
• [ ] LC901. Online Stock Span
• [ ] LC907. Sum of Subarray Minimums
• [ ] Frog Jump II: K steps at most with cost A[i] if landing at position i

In general, the following "prototype" problems can be solved by monotonic queue:

Sliding Max

Any DP problem where S[i] = max(A[j:k]) + C where j < k <= i and C is a constant.

The sliding max/min window problem belongs to this type.

Problem statement: return the max elements in a sliding window of certain length.

Key observation: Given input array A, when A[l] < A[r] for l < r, then A[l] should never be retuned as the sliding max, if A[r] has entered the sliding window.

So we maintain a monotonic array with index increasing and value decreasing.

For example, with sliding window of fixed length 3,

A = [3, 1, 4, 3, 8] => [3], [3, 1], [4], [4, 3], [8] when element 4 enters, we remove [3, 1] because they are on the left and smaller than 4, no chance being chosen as the max element.

The head of the increasing queue is the sliding max!