算法修炼Day60|● 84.柱状图中最大的矩形

class Solution {
  public int largestRectangleArea(int[] heights) {
​    Stack<Integer> stack = new Stack<>();
​    // 数组扩容
​    int[] newHeights = new int[heights.length + 2];
​    newHeights[0] = 0;
​    newHeights[newHeights.length - 1] = 0;
​    for (int i = 0; i < heights.length; i++) {
​      newHeights[i + 1] = heights[i];
​    }
​    heights = newHeights; // 改变数组引用
​    stack.add(0);
​    int result = 0;
​    for (int i = 1; i < heights.length; i++) {
​      if (heights[i] > heights[stack.peek()]) { // 入栈
​        stack.add(i);
​      } else if (heights[i] == heights[stack.peek()]) { 
​        stack.pop(); // 弹出
​        stack.add(i); // 入栈
​      } else {
​        while (heights[i] < heights[stack.peek()]) {
​          int mid = stack.peek(); // 当前数值柱子
​          stack.pop();
​          int left = stack.peek();
​          int right = i;
​          int w = right - left - 1;
​          int h = heights[mid];
​          result = Math.max(result, w * h);
​        }
​        stack.add(i);
​      }
​    }
​    return result;
  }
}