6 minute read

I actually made this name up; I don’t know what it is called. This is how the Chinese call it apparently, 單調棧. It sometimes comes handy when you need O(n) performance in a problem that seemingly needs more than that and which requires finding a number.

Basic facts about monotonic stacks:

  1. It is a kind of precomputation, just like precomputing the prefix sum array.
  2. It is O(n), so it almost never hurts your runtime, just like prefix sum array.
  3. As the name suggests, it is a method that uses a stack (implemented using a vector) that has all elements sorted.
  4. It is used to find the next (or previous) element in the array that is larger (or smaller) than the current element.

Let’s look at the code:

vector<int> lastBigger(vector<int> v) {
    vector<int> ans(v.size()), mono;
    for (int i = 0; i < v.size(); i++) {
        while (!mono.empty() && v[mono.back()] <= v[i])
            mono.pop_back();
        ans[i] = mono.empty() ? -1 : mono.back();
        mono.push_back(i);
    }
    return ans;
}

This piece of code finds the index of the closest previous element that is larger than the current one. For example, for an input vector {1, 5, 4, 2, 3}, it will return {-1, -1, 1, 2, 2}. The index is stored instead of the actual element, because it is more informative and we could look up the actual values from the indices.

The algorithm is based on the idea that to find the last bigger value, we do not need to look at all the previous values. If we go farther to the left, it is because we want a larger value. For example, on the above array, at the last element, we only need to look at the values {5, 4, 2} but not the value 1, because taking 5 is strictly better than taking 1. And after the element 3, 2 will be useless to all future numbers, if there is any. Therefore we keep popping the stack until we find something that is potentially useful for later.

To find a smaller instead of bigger value, simply change <= to >=. To find the next instead of the previous, just start looping from the end to the front.

I have seen this technique come up from time to time from seemingly unrelated problems. I will go through 3 problems.

Sliding Window Maximum

The first problem: given an integer array v of size n and an integer k, return an integer array w of size n-k+1 where w[i] = max(v[i], v[i+1], …, v[i+k-1]).

The most naive thing to do is to run a loop of k times for each element in w, taking the maximum for each value. An obvious observation is that each time we are only moving the window by one index, so the maximum often remains unchanged. So a slight speedup would be to check if the element we are discarding by moving the window is the previous maximum, if not, then we can take the max of the previous maximum and the current value to update the current maximum.

But we are still at worst case O(nk), because if we always discard the maximum, then we need to update the maximum again by looping. Here’s how monotonic stack will compress the runtime to O(n). For each element in w:

  1. Maintain a variable, idx, that stores the index of the maximum element in the previous window.
  2. Move the window to the right by one.
  3. If idx stays in the window, and the new value is larger than the one pointed by idx, update idx to the new index.
  4. If idx stays in the window, and the new value is not larger, then idx remains unchanged.
  5. If idx falls out of the window, first move idx to the right by one. Now it might not be the largest anymore, so we look for the next bigger element. This is O(1), as precomputed by monotonic stack. While the next bigger element is in the window, update idx to point to that element.

The runtime of this algorithm is O(n) because idx and the window only move to the right, and we never go backwards.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if (nums.empty())
        return {};
    vector<int> nextBigger(nums.size(), INT_MAX), mono;
    for (int i = nums.size()-1; i >= 0; i--) {
        while (!mono.empty() && nums[mono.back()] <= nums[i])
            mono.pop_back();
        if (!mono.empty())
            nextBigger[i] = mono.back();
        mono.push_back(i);
    }
    int pt = 0;
    vector<int> ans;
    for (int i = k-1; i < nums.size(); i++) {
        if (pt == i-k)
            pt++;
        while (nextBigger[pt] <= i)
            pt = nextBigger[pt];
        ans.push_back(nums[pt]);
    }
    return ans;
}

There is a 2D version of this problem: given a 2D array v of size n by n and an integer k, return a 2D array w of size n-k+1 by n-k+1 where w[i][j] = max(v[i][j], v[i][j+1], …, v[i][j+k-1], v[i+1][j], …, v[i+k-1][j+k-1]). It is in fact very easy, just run this algorithm twice, first horizontally then vertically. It will be O(n^2), which is optimal as input itself would be O(n^2).

Largest Rectangle in Histogram

This one, although categorized as hard, is fairly straightforward: enumerate elements and use each one as the height, then look for the previous one and the next one that are smaller. Therefore we need to apply monotonic stack twice.

int largestRectangleArea(vector<int>& heights) {
    if (heights.empty())
        return 0;
    vector<int> lastSmaller(heights.size()), nextSmaller(heights.size()), mono;
    for (int i = 0; i < heights.size(); i++) {
        while (!mono.empty() && heights[mono.back()] >= heights[i])
            mono.pop_back();
        lastSmaller[i] = mono.empty() ? -1 : mono.back();
        mono.push_back(i);
    }
    mono.clear();
    for (int i = heights.size()-1; i >= 0; i--) {
        while (!mono.empty() && heights[mono.back()] >= heights[i])
            mono.pop_back();
        nextSmaller[i] = mono.empty() ? heights.size() : mono.back();
        mono.push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < heights.size(); i++)
        ans = max(ans, heights[i]*(nextSmaller[i]-lastSmaller[i]-1));
    return ans;
}

On an irrelevant note, some people like to condense code that should be multiple lines into one line, like squeezing return 0, i++ etc into the previous line. There is no way to be consistent about this, because sometimes the lines get too long and they need to split into two lines. Inconsistent coding style is a sin. It leads to bugs and confusion. Code should be made as short as possible, but no shorter.

132 Pattern

The last problem is fairly new. For these problems, usually we need to enumerate something. In this case, we enumerate the “2”. The algorithm is simple: for each “2”, find “3” by greedy algorithm, and see whether we can find a “1”. The greedy way for “3” is to find the number larger than “2” that is closest to the left of it, which is essentially the last bigger element. Checking whether we can find a “1” is simply finding the range minimum from the left up to “3” and checking whether it is smaller than “2”.

bool find132pattern(vector<int>& nums) {
    if (nums.size() < 3)
        return false;
    vector<int> mins{nums[0]};
    for (int i = 1; i < nums.size(); i++)
        mins.push_back(min(nums[i], mins.back()));
    vector<int> mono, lastbigger(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        while (!mono.empty() && nums[mono.back()] <= nums[i])
            mono.pop_back();
        lastbigger[i] = mono.empty() ? -1 : mono.back();
        mono.push_back(i);
    }
    for (int i = nums.size()-1; i > 1; i--)
        if (lastbigger[i] > 0 && mins[lastbigger[i]] < nums[i])
            return true;
    return false;
}

Now that you have seen the above, you should be able to solve Maximal Rectangle with minimum effort.

Categories:

Updated: