Monotonic-Queue

One-dimensional DP, state-machine DP, DP with a monotonic deque, interval scheduling DP after sorting, deduplicated subsequence counting, and DP-tagged problems where an observation or greedy is faster

LeetCode 1425 note: dp[i] = nums[i] + max(0, max of the previous k dp values); that max is a sliding window maximum, available in O(1) from a monotonic deque

LeetCode 3835 note: cost = (max - min) × length only grows as the window grows, so a sliding window counts subarrays; two monotonic deques keep the window’s max and min

LeetCode 2762 note: a sliding window with two monotonic queues for the window maximum and minimum

LeetCode 1696 note: dp[i] = nums[i] + max of the previous k dp values, with that max kept by a monotonic deque in O(n)

LeetCode Problem Solving

Fixed-size windows, variable windows for longest / shortest, counting subarrays (at most K minus at most K - 1, count += left for at least K), and monotonic deques for window extremes