https://leetcode.com/problems/largest-rectangle-in-histogram

largestRectangle.cc

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int space = 0;
        int maxh = 0;
        int n = heights.size();
        stack<int> s;        
        int i = 0;
        int max_space = 0;
        while(i<n){
            if( s.empty() || ( heights[s.top()] < heights[i])) {
                s.push(i); i++; 
            }
            else{
                int idx = s.top();   
                s.pop();
                int space = heights[idx]*( (!s.empty()) ?  (i-1-s.top()) : i);
                max_space = max(max_space, space);
            }
        }
        while(!s.empty()){
            int idx = s.top();   
            s.pop();
            int space = heights[idx]*( (!s.empty()) ? (n-1-s.top()) : n);
            max_space = max(space, max_space);    
        }
        
        return max_space;
    }
};