美文网首页
LeetCode:84. 柱状图中最大的矩形

LeetCode:84. 柱状图中最大的矩形

作者: alex很累 | 来源:发表于2022-02-27 23:14 被阅读0次

问题链接

84. 柱状图中最大的矩形

问题描述

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

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

示例


解题思路

1. 暴力解法:枚举以每个柱形为高度的最大矩形的面积
依次遍历每个柱形;对于每个柱形,要以这个柱形的高度作为最高高度;同时,我们从这跟柱子开始向两侧延伸,直到遇到高度小于 最高高度 的柱子,就确定了矩形的左右边界。
注:这个解法会超时。

2.单调栈:以解法1的思路为基础,借助单调栈找左右边界
我们需要一个单调递增的栈,遍历柱形高度:
如果当前柱形高度比栈顶元素代表的柱形的高度大,将当前柱形丢到栈里;同时,刚刚的栈顶元素就是它的左边界;
如果当前柱形高度比栈顶元素代表的柱形的高度小,从栈里取出栈顶元素,直到当前柱形高度比栈顶元素大(或栈空了),将当前柱形丢入栈;和上一个步骤一样,这里找到了左边界;另外要注意的是:当前高度是抛出的栈顶元素的右边界;
处理完之后,如果栈里还有元素,他们的右边界是最右边。

代码示例(JAVA)

1. 暴力解法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            // 当前柱形高度为0,跳过
            if (heights[i] == 0) {
                continue;
            }
            int x = i, y = i + 1;
            while (x - 1 >= 0 && heights[x - 1] >= heights[i]) {
                x--;
            }
            while ( y <= heights.length - 1 && heights[y] >= heights[i]) {
                y++;
            }
            int area = (y - x) * heights[i];
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }
}

时间复杂度:O(N2)
执行结果

2.单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);

        Stack<Integer> stack = new Stack();
        // 找左边界, 同时找右边界
        for (int i = 0; i < heights.length; i++) {
            while (!stack.empty() && heights[stack.peek()] >= heights[i]) {
                right[stack.peek()] = i;
                stack.pop();
            }
            left[i] = stack.empty() ? -1 : stack.peek();
            stack.push(i);
        }
        // 栈里剩余的数,右边界就是最右边
        // 也可以在一开始,right数组全给height.length
        // while (!stack.empty()) {
        //     right[stack.peek()] = heights.length;
        //     stack.pop();
        // }
        
        // 找最大矩形
        int maxArea = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            int area = (right[i] - left[i] - 1) * heights[i];
            maxArea = Math.max(maxArea, area);
        }
        
        return maxArea;
    }
}

时间复杂度:O(N)
执行结果

相关文章

网友评论

      本文标题:LeetCode:84. 柱状图中最大的矩形

      本文链接:https://www.haomeiwen.com/subject/spgblrtx.html