84. Largest Rectangle in Histogram

本题我觉得在Hard也许算简单的，但是我依然没有解出，不过没关系，本来也需要适应和学习。
本题需要比较好的抽象能力：
所有valid的面积都是：

当这个同时出现的时候，很容易就能得出的解法。但是本题是要求的解法

思路：

• 设定一个Stack<Integer>，永远保持递增
• 当遇到比peek()更小的元素的时候，需要不断的pop(),直到找到更小的元素，并顺便计算面积
• 本题需要画图才能更好理解
  • 最难的地方是理解对于高度heights[i]的左右边界分别是哪两个index，理解了这个后，本题就非常简单了

• 时间复杂度：

• 空间复杂度:

  class Solution {
  public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxSize = 0;
    for (int i = 0; i < heights.length; ++i) {
      while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
        int height = heights[stack.pop()];
        // left bondry: heights[stack.peek()]; right boundry: i
        int sz = height * (i - (stack.isEmpty() ? 0 : stack.peek() + 1));
        maxSize = Math.max(maxSize, sz);
      }
      stack.push(i);
    }
    while (!stack.isEmpty()) {
      int height = heights[stack.pop()];
      int sz = height * (heights.length - (stack.isEmpty() ? 0 : stack.peek() + 1));
      maxSize = Math.max(maxSize, sz);
    }
    return maxSize;
  }
  }