Dynamic Programming21 sections · 916 units
Open in Course

Increasing vs Decreasing

Choosing the right queue

Use monotonic decreasing queue when you need the maximum in a window. Larger elements dominate smaller ones because they'll always be preferred while both are valid.

Use monotonic increasing queue when you need the minimum in a window. Smaller elements dominate larger ones for the same reason. The Shortest Subarray problem is a special case: you need increasing queue because smaller prefix sums give more "room" for the subarray sum to exceed kk. The structure of your improvement problem determines the monotonicity.