My concise code (20ms, stack based, O(n)), one trick used
The idea is simple, use a stack to save the index of each vector entry in a ascending order; once the current entry is smaller than the one with the index s.top
The idea is simple, use a stack to save the index of each vector entry in a ascending order; once the current entry is smaller than the one with the index s.top(), then that means the rectangle with the height height[s.top()] ends at the current position, so calculate its area and update the maximum. \nThe only trick I use to avoid checking whether the stack is empty (due to pop) and also avoiding emptying the stack at the end (i.e. after going through the vector, s is not empty and we have to consider those in the stack) is to put a dummy "0" at the beginning of vector "height" and the end of "height": the first one makes sure the stack will never be empty (since all the height entries are >=0) and the last one will flush all the remaining non-zero entries of the stack at the end of "for" iteration. This trick helps us keep the code concise.\n\n    class Solution {\n    public:\n        int largestRectangleArea(vector<int>& height) {\n            height.insert(height.begin(),0); // dummy "0" added to make sure stack s will never be empty\n            height.push_back(0); // dummy "0" added to clear the stack at the end\n            int len = height.size();\n            int i, res = 0, idx;\n            stack<int> s; // stack to save "height" index\n            s.push(0); // index to the first dummy "0"\n            for(i=1;i<len;i++)\n            {\n                while(height[i]<height[idx = s.top()]) // if the current entry is out of order\n                {\n                    s.pop();\n                    res = max(res, height[idx] * (i-s.top()-1) ); // note how the width is calculated, use the previous index entry\n                }\n                s.push(i);\n            }\n            height.erase(height.begin()); // remove two dummy "0"\n            height.pop_back();\n            return res;\n        }\n    };
[]