84.柱状图中最大的矩形

讲解链接：代码随想录-84.柱状图中最大的矩形

注意数组扩容。

public int largestRectangleArea(int[] heights) {int[] newHeights = new int[heights.length + 2];System.arraycopy(heights, 0, newHeights, 1, heights.length);int result = 0;Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < newHeights.length; i++) {while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {int mid = stack.pop();int h = newHeights[mid];int w = i - stack.peek() - 1;result = Math.max(result, h * w);}stack.push(i);}return result;
}