柱状图中最大的矩形
力扣链接:84. 柱状图中最大的矩形
题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例
思路
我们先嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体,这个过程是 O(N) 的;
单调增栈,对于栈中的柱体来说,栈中下一个柱体就是左边第一个高度小于自身的柱体。
遍历每个柱体,若当前的柱体高度大于等于栈顶柱体的高度,就直接将当前柱体入栈,否则若当前的柱体高度小于栈顶柱体的高度,说明当前栈顶柱体找到了右边的第一个小于自身的柱体,那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。
这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。头加0不需要判断栈为空,尾加0可以使前面的都出栈。
Java代码
class Solution {
public int largestRectangleArea(int[] heights) {
int[] temp = new int[heights.length + 2];
System.arraycopy(heights, 0, temp, 1, heights.length);
Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for(int i = 0; i < temp.length; i++) {
while(!stack.isEmpty() && temp[i] < temp[stack.peek()]) {
int h = temp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}
return area;
}
}
补充
System.arraycopy使用的基本定义
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
src:源数组;
srcPos:源数组要复制的起始位置;
dest:目的数组;
destPos:目的数组放置的起始位置;文章来源:https://www.toymoban.com/news/detail-442441.html
length:复制的长度.文章来源地址https://www.toymoban.com/news/detail-442441.html
到了这里,关于OJ练习第101题——柱状图中最大的矩形的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!