题目描述:
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
https://leetcode.cn/problems/0ynMMM/description/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=1zqr7v7思路如下:
- 遍历柱子heights，考察所有柱子能向右扩展的最大矩形。在这些对于每一个h来说的最大矩形中，再求最大，即为所求。
- 对当前柱子h进行矩形扩展时，若遇到更矮柱子，此时找到h对应的最大矩形的右边界，结束扩展。但左边界未确定，留待后续说明。
- 对于右边界，如上说明，由h的下一个更矮的柱子所确定。这是典型的单调栈问题。栈保存当前未确定（仍在扩展中）的柱子下标（因为要求面积，需要知道长和宽，宽由下标差得到），当前考察柱 cur = heights[i] 与栈顶柱高h比较，若h < cur，则对h扩展结束，弹出h，并求出矩形面积更新max。
- 此时还需要确定h对应的最大矩形的左边界才能确定该矩形的宽w，进而才能求出面积h * w。由于每次满足h < cur便因为找到右边界而弹出h，因此栈内元素是非递减的，也就是说弹出h后的新栈顶是h左侧的第一个小于h的柱，也就是h对应的最大矩形的左边界，于是宽为 w = i – stack.peek() – 1，若栈空，说明h之前所有柱子都大于h，于是 w = i。此时得到面积为h * w，立即用以更新全局最大面积max。
- 弹出栈顶h后，重复地比较h与当前柱cur，直到h >= cur，cur入栈。在这个过程中max不断得到更新。结束时若栈不为空，则栈内柱仍能更新max。栈内柱的右边界为整个数组的右边界，左边界按照前述说明处理。得到宽w后，继续用h * w来更新max。
代码如下:
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new LinkedList<>();
int maxArea = 0;
stack.push(-1);
for(int i = 0; i < heights.length; i++){
while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
//由于是单调栈,所以找到比栈顶元素小的高度,则找到了栈顶元素
//左右都比他小的元素,目的就是不断寻找栈顶元素量的比站定元素小的数值
int h = heights[stack.pop()];
int width = i - stack.peek() - 1;//注意此处的栈顶元素已经被弹出了
maxArea = Math.max(maxArea, h * width);
}
//统一操作,入栈,即便是弹栈后也要入栈
stack.push(i);
}
//如果遍历结束后还有元素,那么说明栈中的元素,右侧都没有比他们大的数值
//直接拿数组的长度进行面积的计算
while(stack.peek() != -1){
int h = heights[stack.pop()];
int width= heights.length - stack.peek() - 1;
maxArea = Math.max(maxArea, h * width);
}
return maxArea;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88849.html
