Largest Rectangle in Histogram

largetst_rect_in_hist.cpp

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        stack<int> heightSt;
        stack<int> indexSt;  // start index
        
        int maxArea = 0;
        
        height.push_back(0);
        for (int i = 0; i < height.size(); ++i) {
            int h = height[i];
            
            if (i == 0 || h > heightSt.top()) {
                heightSt.push(h);
                indexSt.push(i);
            } else {
                // h <= heightSt.top()
                int startIndex = i;
                while (!heightSt.empty() && h <= heightSt.top()) {
                    startIndex = indexSt.top();
                    int currentHeight = heightSt.top();
                    int currentArea = (i - startIndex) * currentHeight;
                    
                    maxArea = max(maxArea, currentArea);
                    
                    heightSt.pop();
                    indexSt.pop();
                }
                heightSt.push(h);
                indexSt.push(startIndex);
            }
        }
        
        return maxArea;
    }
};