跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

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

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输入： heights = [2,4]
输出： 4

• 类似上一题，只是这里栈顶到栈底的元素是递减的
• 需要数组扩容个，首尾需要加0，比如[2,4,6,7]这种情况需要尾部加0， 比如[8,6,4,2]这种情况需要尾部加0

java">	public int largestRectangleArea(int[] heights) {// 数组扩容，首尾都加0，比如[2,4,6,7]这种情况需要尾部加0， 比如[8,6,4,2]这种情况需要尾部加0int[] newHeight = new int[heights.length + 2];System.arraycopy(heights, 0, newHeight, 1, heights.length);newHeight[heights.length + 1] = 0;newHeight[0] = 0;int res = 0;Stack<Integer> st = new Stack<>();st.push(0);for (int i = 1; i < newHeight.length; i++) {while (newHeight[i] < newHeight[st.peek()]) {int mid = st.pop();// 此时不需要再判空，因为最开始栈里面已经放了0 了int left = st.peek();int w = i - left - 1;res = Math.max(res, newHeight[mid] * w);}st.push(i);}return res;}