Short C++ solution use stack AC 28ms


  • 8
    C
    class Solution {
    public:
        int largestRectangleArea(vector<int>& height) {
            height.push_back(0);
            int result=0;
            stack<int> indexStack;
            for(int i=0;i<height.size();i++){
                while(!indexStack.empty()&&height[i]<height[indexStack.top()]){
                    int top=indexStack.top();
                    indexStack.pop(); 
                    int nextTop=indexStack.size()==0?-1:indexStack.top();
                    result=max((i-nextTop-1)*height[top],result);
                }
                indexStack.push(i);
            }
            return result;
        }
    };

  • 1
    E

    Python version of your idea.

    But I think in the while statement, using ">=" is better to understand than using ">", or in your case, use "<=" instead of "<".

    Although they both passed all the test cases

    def largestRectangleArea(self, height):
        sta = []
        height += [0]
        best = 0
        for i, h in enumerate(height):
            while sta!=[] and height[sta[-1]] >= h:
                top = sta.pop()
                width = i - sta[-1] - 1 if sta!=[] else i
                area = height[top] * width
                best = max(best, area)
            sta.append(i)
            
        return best

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.