## Monotonic Queue Concepts

Summary Usually, the monotonic queue can be used in the following situations. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest…

## Sliding Window & Monotonic Queue

Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…

## Monotonic Queue in DP

Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…

## Monotonic Queue (Pure)

Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…