程序员社区

LeetCode-84-柱状图中最大的矩形

LeetCode-84-柱状图中最大的矩形

84. 柱状图中最大的矩形

难度困难

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

LeetCode-84-柱状图中最大的矩形插图
img

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]

LeetCode-84-柱状图中最大的矩形插图1
img

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

思路

  1. 对于一个高度,如果能得到向左和向右的边界
  2. 那么就能对每个高度求一次面积
  3. 遍历所有高度,即可得出最大面积
  4. 使用单调栈,在出栈操作时得到前后边界并计算面积

能对每个高度(index)求一次面积

  • L:表示左边高度小于当然arr[index]的位置
  • R:表示右边边高度小于当然arr[index]的位置
  • S面积:arr[index]*(R-L-1)
LeetCode-84-柱状图中最大的矩形插图2
image-20210526093404752
LeetCode-84-柱状图中最大的矩形插图3
image-20210526093621261
LeetCode-84-柱状图中最大的矩形插图4
image-20210526093749038

在求L指针和R指针位置时,使用单调栈,在出栈操作时得到前后边界并计算面积

这个算法经过一次遍历,在每一次计算最大宽度的时候,没有去遍历,而是使用了栈里存放的下标信息,以 O(1) 的时间复杂度计算最大宽度。

LeetCode-84-柱状图中最大的矩形插图5
image-20210526094614513
LeetCode-84-柱状图中最大的矩形插图6
image-20210526094914062
LeetCode-84-柱状图中最大的矩形插图7
image-20210526095046372
LeetCode-84-柱状图中最大的矩形插图8
image-20210526095140741
LeetCode-84-柱状图中最大的矩形插图9
image-20210526095239460
LeetCode-84-柱状图中最大的矩形插图10
image-20210526095651525
LeetCode-84-柱状图中最大的矩形插图11
image-20210526095733255
LeetCode-84-柱状图中最大的矩形插图12
image-20210526095753373
class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int maxArea = 0;
        // 只放下标
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {//入栈元素小于栈顶元素,结算面具 右指针i 左指针下一个元素(peek一下)
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);//当前元素入栈,满足(从小到大)单调栈
        }
        while (!stack.isEmpty()) {//所有元素入栈后,结算剩下的面积 右指针:height.length
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (height.length - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}
LeetCode-84-柱状图中最大的矩形插图13
image-20210526100127991

以下列出了单调栈的问题,供大家参考。

1 42. 接雨水(困难) 暴力解法、优化、双指针、单调栈
2 739. 每日温度(中等) 暴力解法 + 单调栈
3 496. 下一个更大元素 I(简单) 暴力解法、单调栈
4 316. 去除重复字母(困难) 栈 + 哨兵技巧
5 901. 股票价格跨度(中等) 股票价格跨度(单调栈)
6 402. 移掉K位数字
7 581. 最短无序连续子数组

赞(0) 打赏
未经允许不得转载:IDEA激活码 » LeetCode-84-柱状图中最大的矩形

一个分享Java & Python知识的社区