LeetCode84.柱状图中最大的矩形
题目链接：LeetCode84
单调栈板子题，创建一个单调递增栈（栈底到栈顶是递增的），栈内存放的数组下标，遍历数组，将下标存进栈内，以样例来说 首先栈空，0直接进栈；然后因为nums[stack.peek()] > nums[1]，所以0出栈了，同时记录以num[0]为高的矩形的面积，当前遍历到的数组下标为i，此时i是1，k等于0出站后，栈顶元素的下标,k= stack.isEmpty() ? -1 : stack.peek()，最终，底的长度就是i-k-1。 如果数组已经遍历到结束了，栈内还有值，就需要将他们依次弹出，此时的i=nums.length()，k=stack.isEmpty() ? -1 : stack.peek()。 整个流程用一个maxArea变量维护，找到最大值即可
class Solution {
public static int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0)
return 0;
int maxArea = 0;
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i < heights.length;i++) {
while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
while(!stack.isEmpty()) {
int i = heights.length;
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录