Use two vector to record left and right indexes that can extend the blocks.

 

1 class Solution { 2 public: 3     int largestRectangleArea(vector
     
       &height) { 4         int len = height.size(), result = 0; 5         vector
      
        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 };