JAVA练习346- 柱状图中最大的矩形

题目概览给定n个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。示例 1:输入heights [2,1,5,6,2,3]输出10解释最大的矩形为图中红色区域面积为 10示例 2输入heights [2,4]输出4提示1 heights.length 10^50 heights[i] 10^4来源84. 柱状图中最大的矩形 - 力扣LeetCode解题分析方法单调栈本题可以看做求每个高度的最大矩形然后返回最大的一个。令当前索引为 i以 [ 2, 3, 1, 4 ] 为例子i 0 时当前高度为 2不能确定最大矩形i 1 时当前高度为 3大于前一个的高度不能确定最大矩形i 2 时当前高度为 1小于前一个的高度因此 i 1高度为 3 的矩形可以确定面积为 3 * ( 2 - 1 )当前高度矩形不能确定因为 i 1 高度为3的矩形已经确定且 i 2 高度为1的高度小于 i 0 的高度高度为2因此 i 0 的矩形面积为 2 * ( 2 - 0 )i 3 时当前高度为 4大于前一个的高度无法确定高度i 4 时越界了此时可以看做高度为 0小于前一个的高度因此 i 3高度为 4 的矩形可以确定面积为 4 * ( 4 - 3 )此时还剩余 高度为 1 的因为 1 最小且其他高度已确定因此面积为 1 * 4得到最大值 4由上面过程可以看出我们实际上关注的是当前高度是否小于前一个的高度因此我们可以定义一个单调递减的栈那么当栈为空时入栈 height [ i ]当 height[ i ] 栈顶元素时入栈 height [ i ]当 height[ i ] 栈顶元素时出栈栈顶元素令索引为 j 若此时栈为空则以 height[ j ] 为高度的最大矩形面积为 height[ j ] * i若此时栈不为空则以 height[ j ] 为高度的最大矩形面积为 height[ j ] * ( i - j - 1)然后继续用栈顶元素重复以上 2、3 操作当 i n 时将 height [ j ] 看做 0重复 3 的操作返回计算过程中最大的矩形面积即可。时间复杂度O(n)空间复杂度O(n)class Solution { public int largestRectangleArea(int[] heights) { int n heights.length; DequeInteger dq new ArrayDeque(); int max 0, i 0; while(i n) { int curHeight i n ? 0 : heights[i]; if (!dq.isEmpty() heights[dq.peek()] curHeight) { int height dq.pop(); int width i; if (!dq.isEmpty()) { width i - dq.peek() - 1; } max Math.max(max, heights[height] * width); continue; } dq.push(i); } return max; } }