leetcode

0 class Solution {

1 public:

2 int largestRectangleArea(vector<int> &heights) {

3 int n = heights.size();

4 vector<int> left(n), right(n);

5 stack<int> st;

6

7 for (int i = 0; i < n; i++) {

8 left[i] = i;

9 while (!st.empty() && heights[st.top()] >= heights[i]) {

10 left[i] = left[st.top()];

11 st.pop();

12 };

13 st.push(i);

14 }

15

16 for (int i = n - 1; i >= 0; i--) {

17 right[i] = i;

18 while (!st.empty() && heights[st.top()] >= heights[i]) {

19 right[i] = right[st.top()];

20 st.pop();

21 };

22 st.push(i);

23 }

24

25 int res = 0;

26 for (int i = 0; i < n; i++)

27 res = max(res, (right[i] - left[i] + 1) * heights[i]);

28 return res;

29 }

30 };