X

leetcode 84. Largest Rectangle in Histogram 解题思路分析

题目大意:

柱状图中最大的矩形

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

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

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

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

示例:

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

解题思路:

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=84

本题介绍两种解法:

  1. 贪心算法。(执行速度快)
  2. Stack。(执行速度慢于贪心,但作为一种经典算法需要了解一下)

先说贪心算法,其思想与之前介绍过的 子数组的最小值之和 这道题一模一样。简单说下思路:

  1. 连续柱的最大面积取决于最矮柱的高度,所以我们可以将当前柱设为最矮,即求出当前柱左右两边各有多少连续比自己高的柱,两边的范围长度乘以当前柱的高度,就是包含当前柱情况下能取得的最大矩形面积。
  2. 以上面的思路循环遍历数组中所有柱的高度,求出的最大面积即是答案。
  3. 这个解法的关键是如何求出左右两边连续比自己大的数,注意是连续,比如当前位的高度为5,之后存在{6, 7, 8, 3, 9, 10},连续的意思是{6, 7, 8}是符合条件的范围。具体的逻辑可以参考 子数组的最小值之和 这篇文章。这里只给出实现代码,代码中就不做注释讲解了。
public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) {
        return 0;
    }
    int[] leftBiggerCount = new int[heights.length];
    for (int i = 0; i < heights.length; i++) {
        int count = 1;
        int index = i - 1;
        while (index >= 0 && heights[index] > heights[i]) {
            count += leftBiggerCount[index];
            index -= leftBiggerCount[index];
        }
        leftBiggerCount[i] = count;
    }
    int[] rightBiggerCount = new int[heights.length];
    for (int i = heights.length - 1; i >= 0; i--) {
        int count = 1;
        int index = i + 1;
        while (index < heights.length && heights[index] >= heights[i]) {
            count += rightBiggerCount[index];
            index += rightBiggerCount[index];
        }
        rightBiggerCount[i] = count;
    }
    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        max = Math.max(max, (rightBiggerCount[i] + leftBiggerCount[i] - 1) * heights[i]);
    }
    return max;
}

接下来说下Stack的算法。

Stack也就是栈, 插入与删除操作只能在其头部进行,所以按照后进先出的逻辑运行。结合本题,大致的实现思想如下:

一,如果当前高度大于等于栈顶数值(上一次插入的值)高度,那么将当前高度入栈。保证栈中的数字是有小到大排列。

二,如果当前高度小于栈顶数值高度,将栈顶数值出栈,直到栈顶数值高度小于当前值为止。我们称之为进行了一组出栈运算。每出栈一个数,都要计算一次被出栈数在当前组中能够组成的最大面积。计算公式为:出栈数 * 出栈顺序(顺序从1开始计数)。举个例子:

// 栈中已经存在如下高度
{2, 4, 5, 6}
// 接下来需要插入高度3,那么按照顺序6,5,4将出栈,所有在出栈时计算面积应该为:
6 * 1 = 6
5 * 2 = 10
4 * 3 = 12

以上做法的原因是,当当前高度小于栈顶高度时进行出栈操作,此时,栈顶高度可以被看作是一个临时波峰,以波峰为界限向左边看,能形成的矩形应该分别是6自己这根柱,5和6组合成2个5的面积,4,5,6组成3个4的面积。那么,为什么2不参与到计算中来,因为2还没有被出栈,每组出栈的数字以后不会再次被加入到栈中,因此这部分的计算应该在出栈时完成,尚存在栈中的数字,以后还有机会再次被计算。

三,接下来问题来了,在4,5,6出栈后,下一个数字是3,如果3加到2的后面,那么2和3之间的距离就变成了1,而不是原先的4,所以在push3进栈之前,应先将已出栈的位置使用当前数字(也就是例子中的3)填满,这样既保证了3与2之间的间隔正确,同时还保证了栈中的数字是从小到大排序。不过,有人会问,用3填满之前的空是否会影响计算呢?答案是不会影响。因为计算面积是以最矮高度计算的,3之前原先的数字是4,5,6,均大于3,所以不论以3为起点向左计算面积,还是以2开始向左计算面积,均不会影响到结果(所以此处用2填满同样可以)。

四,最后需要注意一点,本算法是遇到比栈顶数字小的时候出发出栈运算,所有的面积计算均在出栈时完成,这样会存在一个漏洞,如果数组最后一位大于栈顶数字,这时循环结束后栈中剩下的数字就没有机会计算面积了。因此,为了避免这种情况发生,我们在题目给定的数组最后加上一个0,保证最后一个数入栈后可以进行出栈操作。

总结,用栈来模拟,遍历heights数组,如果大于栈顶元素,就push进去;否则,持续弹栈来计算从栈顶点到降序点的矩阵大小。然后将这一部分全部替换为降序点的值,即做到了整体依然是有序非降的。整个过程中,分别将每一个点作为起点,到各个波峰的面积都计算过一次,因此保证了每个点作为起点存在的最大面积都计算过。

最后看下代码:

public int largestRectangleArea(int[] heights) {
    Stack<Integer> heightStack = new Stack<>();
    heights = Arrays.copyOf(heights, heights.length + 1);
    heights[heights.length - 1] = 0;
    int max = 0;
    for (int h : heights) {
        if (heightStack.isEmpty() || heightStack.peek() <= h) {
            heightStack.push(h);
        } else {
            int index = 1;
            while (!heightStack.empty() && heightStack.peek() > h) {
                max = Math.max(max, heightStack.pop() * index++);
            }
            for (int i = 0; i < index; i++) {
                heightStack.push(h);
            }
        }
    }
    return max;
}

贪心算法的执行时间为2ms:

Stack算法的执行时间为15ms

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-84-largest-rectangle-in-histogram-解题思路分析/
Categories: leetcode
admin:

View Comments (0)