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-解题思路分析/