LeetCode – Refresh – Largest Rectangle in Histogram

 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4         int len = height.size(), result = 0;
 5         vector<int> left(len), right(len);
 6         for (int i = 0; i < len; i++) {
 7             left[i] = i;
 8             while (left[i] > 0 && height[i] <= height[left[i]-1]) left[i] = left[left[i]-1];
 9         }
10         for (int i = len-1; i >= 0; i--) {
11             right[i] = i;
12             while (right[i] < len-1 && height[i] <= height[right[i]+1]) right[i] = right[right[i]+1];
13         }
14         for (int i = 0; i < len; i++) {
15             result = max(result, height[i] * (right[i] - left[i] + 1));
16         }
17         return result;
18     }
19 };