Monotonic Stack

Last updated 3 years ago

Was this helpful?

Monotonic Stack

A monotonic stack is a stack whose elements are monotonically increasing or descreasing.

Sometimes we store the index of the elements in the stack and make sure the elements corresponding to those indexes in the stack forms a mono-sequence.

Increasing or decreasing?

If we need to pop smaller elements from the stack before pushing a new element, the stack is decreasing from bottom to top.

Otherwise, it's increasing from bottom to top.

For example,

Mono-decreasing Stack

Before: [5,4,2,1]
To push 3, we need to pop smaller (or equal) elements first
After: [5,4,3]

Notes

For a mono-decreasing stack:

we need to pop smaller elements before pushing.
it keep tightening the result as lexigraphically greater as possible. (Because we keep popping smaller elements out and keep greater elements).

Both nextSmaller and prevSmaller

If we need to calculate both nextSmaller and prevSmaller arrays, we can do it using a mono-stack in one pass.

// OJ: https://leetcode.com/problems/largest-rectangle-in-histogram/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int largestRectangleArea(vector<int>& A) {
        A.push_back(0); // append a zero at the end so that we can pop all elements from the stack and calculate the corresponding areas
        int N = A.size(), ans = 0;
        stack<int> s; // strictly-increasing mono-stack
        for (int i = 0; i < N; ++i) {
            while (s.size() && A[i] <= A[s.top()]) { // Take `A[i]` as the right edge
                int height = A[s.top()]; // Take the popped element as the height
                s.pop();
                int left = s.size() ? s.top() : -1; // Take the element left on the stack as the left edge
                ans = max(ans, (i - left - 1) * height);
            }
            s.push(i);
        }
        return ans;
    }
};

Problems

PreviousMono Deque NextOffline Query

Last updated 3 years ago

Was this helpful?