class Solution { public: int largestRectangleArea(vector<int> &height) { // Start typing your C/C++ solution below // DO NOT write int main() function if(height.empty()) return 0; int N = height.size(); vector<int> left(N, 0); vector<int> right(N, 0); stack<int> s1; s1.push(0); for(int i = 1; i < N; i++){ if(height[i] > height[s1.top()]){ left[i] = 0; }else{ while(!s1.empty() && height[i] <= height[s1.top()]){ s1.pop(); } if(s1.empty()){ left[i] = i; }else{ left[i] = i-s1.top()-1; } } s1.push(i); } stack<int> s2; s2.push(N-1); for(int i = N-2; i >= 0; i--){ if(height[i] > height[s2.top()]){ right[i] = 0; }else{ while(!s2.empty() && height[i] <= height[s2.top()]){ s2.pop(); } if(s2.empty()){ right[i] = N-i-1; }else{ right[i] = s2.top()-i-1; } } s2.push(i); } for(int i = 0; i < N; i++){ left[i] =(left[i] + right[i] + 1) * height[i]; } return *max_element(left.begin(), left.end()); } };