给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入: [2,1,5,6,2,3]
输出: 10

image.png

public int largestRectangleArea(int[] h) {
  int n = h.length, i = 0, max = 0;
    
  Stack<Integer> s = new Stack<>();//单调增栈
    
  while (i < n) {
    //当栈顶元素小于当前元素是弹栈，直到当前元素大于栈顶元素为止
    while (!s.isEmpty() && h[i] < h[s.peek()]) {
     //由于是单调栈，栈中元素都小于等于栈顶，所以可以以栈里当前元素的下标和i的差值作为矩形的宽
      //因为i实际就是原来栈顶的下标加一
      max = Math.max(max, h[s.pop()] * (i - (s.isEmpty() ? 0 : s.peek() + 1)));
    }
    // put current bar's index to the stack
    s.push(i++);
  }
    
 
  while (!s.isEmpty()) {
    max = Math.max(max, h[s.pop()] * (n - (s.isEmpty() ? 0 : s.peek() + 1)));
  }
    
  return max;
}