熟悉的味道, 跟这道题一摸一样的解法。

对于每个i:
  找i左右两侧离i最近的比i低的柱子j和k, j<i<k, h[j]<h[i]>h[k]
  以height[i]为高的矩形的最大宽度为(k-j-1)

时间: O(n)
空间: O(n)

import java.util.*;

public class Solution {
  public int largestRectangleArea (int[] heights) {
    // mem[i][0] = j, mem[i][1] = k
    int[][] mem = new int[heights.length][2];
    
    // 从左向右，单调递增栈, 找j (i.e. i左侧离i最近的比i低的)
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < heights.length; i++) {
      while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
        stack.pop();
      }
      mem[i][0] = stack.isEmpty() ? -1 : stack.peek();
      stack.push(i);
    }
   
    // 从右向左，单调递增栈，找k (i.e. i右侧离i最近的比i低的)
    stack = new ArrayDeque<>();
    for (int i = heights.length-1; i >= 0; i--) {
      while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
        stack.pop();
      }
      mem[i][1] = stack.isEmpty() ? heights.length : stack.peek();
      stack.push(i);
    }
    
    // 对于每个i求以height[i]为高的最大矩形面积，然后取个max就行
    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
      // a(i) = h * w = h[i] * (k-j-1))
      int area = heights[i] * (mem[i][1] - mem[i][0] - 1);
      maxArea = Math.max(maxArea, area);
    }
    return maxArea;
  }
}