Let's solve the leetcode problem Largest Rectangle in Histogram.

This is a pretty hard problem, which has multiple solutions.

The most straightforward way is to use brute force, which has time complexity as O(n^2).

class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {
    int res{0};
    for (int i = 0; i < heights.size(); i++) {
      int minHeight = heights[i];
      for (int j = i; j < heights.size(); j++) {
        minHeight = min(minHeight, heights[j]);
        res = max(res, minHeight * (j - i + 1));
      }
    }
    return res;
  }
};

Another improved solution is called divide and conquer, which has the time complexity as O(n*log(n)).

The idea is, find the maximum of below 3 cases:

1. The max area if we use the current minimum element as the height

2. The max area on the left of the current minimum element

3. The max area on the right of the current minimum element

So as you can see, it is a recursive process.

class Solution {
  int util(vector<int>& heights, int left, int right) {
    if (left > right) return 0;

    int minHeightI = left;
    for (int i = left + 1; i <= right; i++) {
      if (heights[i] < heights[minHeightI]) {
        minHeightI = i;
      }
    }

    return max(heights[minHeightI] * (right - left + 1),
               max(util(heights, left, minHeightI - 1),
                   util(heights, minHeightI + 1, right)));
  }

 public:
  int largestRectangleArea(vector<int>& heights) {
    return util(heights, 0, heights.size() - 1);
  }
};

We could use a stack to achieve O(N).

The key is to take each bar as current height and extend to the left and right as far as possible.

Take an example: [6,7,5,2,4,5,9,3]:

Now for element x, the max areas it could get is:

6 => [6,7] => 6*2 => 12
7 => [7] => 7*1 => 1
5 => [6,7,5] => 5*3 => 15
2 => [6,7,5,2,4,5,9,3] => 2*8 => 16
4 => [4,5,9] => 4*3 => 12
5 => [5,9] => 5*2 => 10
9 => [9] => 9*1 => 9
3 => [4,5,6,3] => 3*4 => 12

So for each element as current height, we need to find the left boundary and the right boundary, then we can calculate the max area for the current element as height.

So the question becomes how to find the left boundary and right boundary efficiently.

The idea is to make use of the monotonic stack data structure. You can check my previous article Monotonic Stack to get to know some details.

The process is, we maintain a monotonic increasing stack when we iterate the array. Because it is a monotonic increasing stack, so we will always have the left boudary, which is the left element of the current element. Then whenever we have a new element whose value is smaller than the one on the top of the stack, now we know we have the right boundary. When we hit the right boundary, we will pop the stack, until the new element is not smaller than the element on top. When we are popping the element, because we know the left boundary and right boundary of the popped element, we should be able to calculate its area.

A few things we need to take note of during the process.

First, we need to store the index of the array into the stack. So when we are popping the element, we would be able to know the distance between popped element and the new element, so we can calculate the area.

Second, the bottom element in the stack is the special case. Remember we said that the left element of the current element is the left boundary. But the bottom element on stack does not have left element. In this case, the left boundary of the bottom element can actually extend to the start of the array. So its left boundary is the start of the array.

Third, when the iteration is done and the stack is not empty. We will know the right boundary and we need to pop all the remaining elements and calculate its area.

With all this information, we should be able to come up with the solution.

class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {

    stack<int> stk;

    // -1 as the bottom element for
    // 1. indicate that the stack is empty
    // 2. to calculate the left boundary for first elemnt easily
    stk.push(-1);

    int max_area = 0;

    for (size_t i = 0; i < heights.size(); i++) {

      // new element smaller than the element on top
      while (stk.top() != -1 and heights[stk.top()] >= heights[i]) {
        int current_height = heights[stk.top()];
        stk.pop();

        // right boundary: new element
        // left boundary: the element on the left
        int current_width = i - stk.top() - 1;
        max_area = max(max_area, current_height * current_width);
      }

      // keep maintaining the monotomic increasing stack
      stk.push(i);
    }

    // when the iteration is done and the stack is not empty
    while (stk.top() != -1) {
      int current_height = heights[stk.top()];
      stk.pop();

      // right boundary: the end of the array
      // left boundary: the element on the left
      int current_width = heights.size() - stk.top() - 1;
      max_area = max(max_area, current_height * current_width);
    }

    return max_area;
  }
};