给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
题解
直接说官方题解的思路，已测试用例【2,1,5,6,2,3】来说，在左侧-1，和6的索引上各新增一个虚拟节点，值为0。
从左开始遍历，我们可以先在栈中压入一个-1作为打底。此处用Deque代替Stack使用，根据网友的说法Java 因为历史的原因 Stack 这个类设计得不好，官方建议使用Deque，只使用特定的方法从队位插入，从队尾弹出来模拟实现。具体可能需要看下Stack的底层源码实现。
0）回归正题，当索引走到0的时候，对应的值2，对比栈顶当前索引-1对应的值0，2>0，那么我们直接把索引0压入栈。此时栈中情况为-1,0
1）当索引到1的时候对应的值1，对比栈顶索引0，对应的值2，1<2，将2弹出，找到2高度为当前的2的时候能取得的最大面积的宽度，为当前的的索引1到当前栈顶0取出后的栈顶索引0之间的距离，为1。所以2对应的面积为2×1 = 2，对应索引0。
在索引0弹出后，将索引1压入栈，当前栈中的情况为-1,1
2）继续遍历下一个当前索引2，对应的值为5,对比栈顶索引1对应的值1，5大于1，所以直接压入栈。
3）继续遍历下一个当前索引3，对应的值为6，对比当前栈顶索引2对应的值5，6大于5，直接压入栈。
4）继续遍历下一个，当前索引4，对应的值2，2比6小，弹出栈顶索引3，并得到对应宽度为栈顶索引3弹出后的栈顶索引位置2，那么宽度就是4到2之间的距离个数4-2-1为1个，于是得到了当前位置的6对应的最大面积6×1=6。
到目前位置已经知道的索引0位置的2对应的面积2，索引3位置的6对应的面积6。那么当前的最大面积就是6了。
在索引3位置的6弹出后，当前索引4位置的2依旧还要和当前栈顶索引2的5对比。而5大于2，继续做相同的处理，将索引2弹出，栈中索引2的前一个索引是1，所以2位置的5对应的面积为5x(4-1-1) = 10。此时最大值面积为10。
直到栈顶索引1对应的值1小于当前索引4对应的值2，将当前索引4压入栈
5）下一个循环，当前索引5，对应的值3，比当前栈顶索引4对应的值2大，直接压入栈
6）再下一个循环，数组部分的值已经结束，当前索引6，对应的值为我们之前虚拟的值0，而0小于3。弹出栈顶索引5，索引5对应的值为3，栈中索引5的前一个是索引4，那么可以知道索引5的高度3对应能取到的最大宽度为6-4-1 = 1，对应面积为3。当前最大面积依旧是10。
在栈顶索引5弹出后，当前栈顶索引是4，对应的值2也大于0，继续弹出栈顶索引4，对应值2。同样的，栈顶索引4的前一个是1，当前位置的2能取得的最大宽度是6-1-1 = 4，最大面积为2×4 =8。最大面积还是10。
索引4弹出后，继续往前对比索引1，1大于0，同样的操作。
最终结束。
下面是代码
import java.util.ArrayDeque;
import java.util.Deque;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
private int max = 0;
private int[] arr;
public int largestRectangleArea(int[] heights) {
arr = heights;
Deque<Integer> deque = new ArrayDeque<>();
deque.offer(-1);
for (int i = 0; i <= arr.length; i++) {
int num = getNumByIndex(i);
int dequeLastIndex = deque.peekLast();
int dequeLastNum = getNumByIndex(dequeLastIndex);
if (num >= dequeLastNum){
//这边deque.offer(i)和下面else里的deque.offer(i)其实可以合并，
// 将if判断条件取反执行else里的逻辑，并最终都if外deque.offer(i)
deque.offer(i);
}else {
while (!deque.isEmpty() && getNumByIndex(deque.peekLast())>num){
dequeLastIndex = deque.pollLast();
//最终终止边界不好判断的话，可以直接在这里判断-1索引终止
if (dequeLastIndex == -1){
return max;
}
dequeLastNum = getNumByIndex(dequeLastIndex);
int length = i - deque.peekLast() - 1;
int area = dequeLastNum * length;
max = Math.max(area,max);
}
deque.offer(i);
}
}
return max;
}
private int getNumByIndex(int index){
if (index==arr.length || index==-1){
return 0;
}
return arr[index];
}
}
//leetcode submit region end(Prohibit modification and deletion)
发表评论