AntInLoop

Monotonic Stack & Monotonic Queue Patterns

Monotonic Stacks and Monotonic Queues maintain elements in sorted order by discarding dominated entries, solving Next Greater Element, Daily Temperatures, Histogram Area, and Sliding Window Max in O(n).

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Monotonic Stack & Monotonic Queue Patterns

A Monotonic Stack or Monotonic Deque keeps elements in strictly increasing or decreasing order by popping any element that is permanently dominated by the newcomer. Because every index enters once and leaves at most once, the amortized runtime is strictly $O(n)$!

At a Glance

| Structure | Maintains | Classic Problems |

| :--- | :--- | :--- |

| Monotonic Stack | Nearest smaller/greater element to left/right | Daily Temperatures, Stock Span, Largest Rectangle in Histogram, Sum of Subarray Minimums |

| Monotonic Deque | Min/max over a sliding window [l, r] | Sliding Window Maximum, Shortest Subarray with Sum $\ge K$, DP with sliding-window transitions |

---

Practice Problems

Intermediate

1. Daily Temperatures (LeetCode 739)

Given daily temperatures T[], return how many days you must wait after day i for a warmer temperature (0 if none).

Approach: Decreasing monotonic stack of indices; whenever T[i] > T[st.top()], ans[st.top()] = i - st.top(). Time: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <stack>
#include <vector>

std::vector<int> dailyTemperatures(const std::vector<int>& T) {
    int n = static_cast<int>(T.size());
    std::vector<int> ans(n, 0);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && T[i] > T[st.top()]) {
            ans[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

int main() {
    for (int d : dailyTemperatures({73, 74, 75, 71, 69, 72, 76, 73})) std::cout << d << " ";
    std::cout << "\n"; // 1 1 4 2 1 1 0 0
    return 0;
}

</details>

---

Related Structures & Algorithms