Monotonic Stack and Monotonic Queue

Maintain increasing/decreasing candidates while removing elements that can no longer be answers.

Concepts

Maintain increasing/decreasing candidates while removing elements that can no longer be answers.

Problems

Next greater element, next smaller element, daily temperatures, stock span, largest histogram rectangle, maximal rectangle, sliding-window maximum, shortest subarray variants, and contribution counting for subarray minima/maxima.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> t = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> wait(t.size(), 0);
    stack<int> st;                                       // indices with decreasing temperatures
    for (int i = 0; i < (int)t.size(); ++i) {
        while (!st.empty() && t[st.top()] < t[i]) { wait[st.top()] = i - st.top(); st.pop(); }
        st.push(i);
    }
    cout << "days until warmer:";
    for (int w : wait) cout << ' ' << w;

    // sum of minimums of all subarrays: each a[i] is the minimum of left[i] * right[i] subarrays
    vector<long long> a = {3, 1, 2, 4, 1};
    int n = (int)a.size();
    vector<long long> left(n), right(n);
    stack<int> s1, s2;
    for (int i = 0; i < n; ++i) {                        // previous strictly smaller
        while (!s1.empty() && a[s1.top()] >= a[i]) s1.pop();
        left[i] = i - (s1.empty() ? -1 : s1.top()); s1.push(i);
    }
    for (int i = n - 1; i >= 0; --i) {                   // next smaller-or-equal: ties counted once
        while (!s2.empty() && a[s2.top()] > a[i]) s2.pop();
        right[i] = (s2.empty() ? n : s2.top()) - i; s2.push(i);
    }
    long long fast = 0, brute =
…

days until warmer: 1 1 4 2 1 1 0 0
sum of subarray minimums of {3,1,2,4,1}: 22 (brute force 22)

Advanced details

Handle duplicates with carefully chosen strict/non-strict comparisons. Explain why each element is pushed and popped at most once, giving linear total work.

In the contribution count, one side uses >= and the other >. With two equal minimums (the 1s), the subarray covering both is assigned to exactly one of them; using >= on both sides would count it twice, and > on both would miss it.

Quiz

? Why does the daily-temperatures loop run in O(n) total?
+ Each index is pushed once and popped at most once. :: The inner while loop's total work is bounded by n.
- The while loop runs at most once per i. :: It can pop many.
- Temperatures are bounded. :: Irrelevant.
- Because the stack is small. :: It can hold n indices.

? Using strict comparison on one side and non-strict on the other in contribution counting…
+ assigns each subarray with tied minimums to exactly one occurrence :: Avoids double counting or missing.
- is a style choice :: It changes the answer.
- breaks for distinct values :: Distinct values are unaffected.
- sorts the array :: No.

? A monotonic deque is to sliding-window maximum as a monotonic stack is to…
+ next greater element :: Both discard dominated candidates.
- binary search :: Different technique.
- hashing :: No.
- merge sort :: No.