84.柱状图中最大的矩形
题目链接/文字讲解：柱状图中最大的矩形
题设：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution {
public int largestRectangleArea(int[] heights) {
int[] newHeight = new int[heights.length + 2];
System.arraycopy(heights, 0, newHeight, 1, heights.length);
newHeight[heights.length+1] = 0;
newHeight[0] = 0;
Stack<Integer> stack = new Stack<>();
stack.push(0);
int res = 0;
for (int i = 1; i < newHeight.length; i++) {
while (newHeight[i] < newHeight[stack.peek()]) {
int mid = stack.pop();
int w = i - stack.peek() - 1;
int h = newHeight[mid];
res = Math.max(res, w * h);
}
stack.push(i);
}
return res;
}
}
