Largest Rectangle in Histogram [Leetcode]

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution: a straightforward way is brute force, which means for each element, we walks towards both sides and find the first one lower than current element in each side, then compute the area. we take bar 2 with height of 5 as an example. The first one lower than bar 2 in the left side is bar i=1; the first one lower than bar 2 in the right side is bar j=4. so the area is (j-i-1)*5, i.e., 10. In this way, it is easy to find out the maximum area. But here I do not want to give an implementation of this solution since there is a more elegant one as follows (I get it online).

Let's reconsider this problem, we want a linear time algorithm by scanning the entire array exactly one. When we want to compute the area of the largest rectangle with the height of height[i] (bar i), we need to know the position of the first element lower than bar i (counting from i towards beginning) in the left side; here we use a stack to remember this. Check here to get the complete algorithm. It is to be noted that the algorithm is linear since each bar is pushed and popped exactly once.

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(height.empty()) return 0;
        //adding a dummy bar with height -1.
        height.push_back(-1);
        int maxSum = 0, n=height.size();
        stack<int> s;
        for(int i=0; i<n; ++i){
            while(!s.empty() && height[i]<height[s.top()]){
                int curIndex = s.top();
                s.pop();
                int numBar = (s.empty()?i:i-s.top()-1);
                maxSum = max(maxSum, height[curIndex]*numBar);
            }
            s.push(i);
        }
        return maxSum;
    }
};