Monotonic Stack and Queue: the Next Greater Element and the Window Minimum

Lesson 3 of 7 · Advanced techniques

A stack or a queue in which the elements are always ordered by size (monotonically) solves in O(n) tasks that naively need O(n²): "the first greater element to the right", "the largest rectangle in a histogram", "the minimum of every window of length k".

Before you start: prior knowledge you need – stack (SR), queue (SR), two pointers.
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The next greater element

For every element of the array we need to find the first element to its right that is greater (or −1). We go from left to right and keep on a stack the positions of the elements for which a greater one has not been found yet; their values on the stack are decreasing. When a new element a[i] arrives, it is the "next greater" for all elements on the top of the stack that are smaller than it – we pop them.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), answer(n, -1);
    for (int &x : a) cin >> x;
    stack<int> st;                         // positions without a greater element found; the values decrease
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            answer[st.top()] = a[i];       // a[i] is the first greater element for the one on top
            st.pop();
        }
        st.push(i);
    }
    for (int i = 0; i < n; i++) cout << answer[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

For the input 6 / 2 1 5 3 4 1 the program prints 5 5 -1 4 -1 -1.

Every element is pushed onto the stack once and popped at most once, so the total is O(n), even though there is an inner while loop.

The largest rectangle in a histogram

We are given bars of heights h[0..n−1] and width 1. The largest rectangle that fits into the histogram has the height of some bar h[i] and stretches left and right as long as the bars are at least that high. With a monotonic stack, in one pass, we find for every bar the first lower bar on the left and on the right.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;
    vector<int> left(n), right(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {                 // the first lower bar on the left
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {            // the first lower bar on the right
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long best = 0;
    for (int i = 0; i < n; i++)
        best = max(best, h[i] * (right[i] - left[i] - 1));   // the width between the lower neighbours
    cout << best << endl;
    return 0;
}

For the heights 2 1 5 6 2 3 the program prints 10 (the bars 5 and 6, height 5, width 2).

The minimum of every window: a monotonic queue (deque)

For every contiguous part (a "window") of length k we need to print the smallest element. In a double-ended queue (deque) we keep positions whose values are increasing: the minimum of the window is at the front. A new element removes from the back all elements greater than itself (they will never be the minimum again), and from the front we remove the positions that have left the window.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    deque<int> dq;                                // positions; the values grow from the front to the back
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();   // larger ones are no longer candidates
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();  // it has left the window [i-k+1, i]
        if (i >= k - 1) cout << a[dq.front()] << (i + 1 < n ? " " : "\n");
    }
    return 0;
}

For the input 8 3 / 1 3 -1 -3 5 3 6 7 the program prints -1 -3 -3 -3 3 3.

Here too every element enters once and leaves once – O(n). For the maximum of the window, just reverse the comparison.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: medium

For how many days was the price lower?

For every day we are given the price of a share. For every day print for how many consecutive days, ending with that day, the price was less than or equal to today's (including today).

Example

Input

7
100 80 60 70 60 75 85

Output

1 1 1 2 1 4 6
TASK 02Difficulty: easy

The warmest period

We are given temperature measurements for n days and a number k. For every period of k consecutive days print the highest temperature.

Example

Input

6 2
3 1 4 1 5 9

Output

3 4 4 5 9
Common mistakes and tips
  • Put positions on the stack/queue, not values – that way you also know how far away an element is and whether it has left the window.
  • Before st.top() always check that the stack is not empty.
  • Decide whether the condition for popping should be < or <= – the difference is in how equal elements are treated.

Check your knowledge

Open the quiz

Monotonic stack and queue

1. What is the complexity of finding the next greater element with a monotonic stack?




2. What is at the front of a monotonic queue for the window minimum?




3. Which C++ structure allows adding and removing at both ends?