1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.size() <= 0) return 0;
        height.push_back(-1);
        int max = 0x80000000;
        vector<int> stack;
        stack.clear();
        stack.push_back(0);
        for(int i = 1; i < height.size(); i++) {
            if(height[stack[stack.size()-1]] <= height[i]) stack.push_back(i);
            else {
                while(stack.size() > 0 && height[stack[stack.size() - 1]] > height[i]) {
                    int heighttmpi = stack[stack.size()-1];
                    stack.pop_back();
                    if(stack.size() == 0) {
                        if(height[heighttmpi] * (i-0) > max) max = height[heighttmpi] * (i-0);
                    }
                    else {
                        if(height[heighttmpi] * (i-stack[stack.size()-1]-1) > max) max = height[heighttmpi] * (i-stack[stack.size()-1]-1);
                    }
                }
            }
            stack.push_back(i);
        }
        return max;
    }
};