阅读 27

LeetCode柱状图中最大的矩形

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

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

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

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

示例:

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

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/la…

解题思路

1. 循环2次,获取高度最小的值乘以相间隔的距离得出面积。用Math.max方法,找出最大值。效率太低了。

public int largestRectangleArea(int[] heights) {
    int max = Integer.MAX_VALUE;
    int area = 0;
    for (int i = 0; i < heights.length ; i++) {
        for (int j = i; j < heights.length; j++) {
            max = Math.min(max, heights[j]);
            area = Math.max(area, max * (j-i+1));
        }
    }
    return area;
}
复制代码

使用栈的方法

  1. 定义栈,加入初始值-1.
  2. 循环数组,判断栈中的元素不等于初始值,并且通过栈中的下标找到的值大于当前的值,就将数据出栈,使用heights[栈中取出的最后入栈的值的下标] 乘以当前循环次i减去栈中倒数第二个下标在减一。算出最大的面积。

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        while(stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
            max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
        }
        stack.push(i);
    }
    while(stack.peek() != -1) {
        max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
    }
    return max;
}
复制代码
关注下面的标签,发现更多相似文章
评论