LeetCode84柱状图中最大的矩形

发表于 | 更新于 | 分类于 |
超时与未超时，两种思路解决柱状图中最大的矩形

题目描述：

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

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

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

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

示例:

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

解题思路：

思路一：

这个方法是一个超时的方法。

因为要求所能围成的矩形的最大面积，而所围成的矩形的高度，肯定是来自于列表中矩形的高度。所以只需要求得不同高度的矩形所能围成的最大矩形面积即可。

需要使用两次遍历，外层遍历是使用的矩形的高度，内层是对所有矩形进行遍历，求得使用当前高度所能围成的矩形的面积。使用上例，当前高度为2时，当前高度所能围成的矩形有两个，如下图：

每次计算均需重复遍历一遍列表，算法的复杂度为 $O(n^2)$

代码实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def largestRectangleArea(heights):
    """
    :type heights: List[int]
    :rtype: int
    """
    if len(heights) == 0:
        return 0

    h = max(heights)
    s = min(heights)
    ans = 0

    for i in range(s, h + 1):
        start = end = 0
        flag = False

        for j in range(len(heights)):
            if heights[j] >= i:
                end = j + 1
                flag = True
            else:
                if flag:
                    temp = (end - start) * i
                    if temp > ans:
                        ans = temp
                    start = j + 1
                    flag = False
                else:
                    start = j + 1
                    flag = False

            if j == len(heights)-1 and flag:
                temp = (end - start) * i
                if temp > ans:
                    ans = temp

    return ans

思路二：

这是一个正确的方法，算法的复杂度为 $O(n)$

需要遍历一次数组，使用栈来操作已经遍历过的矩形。栈中保存的是遍历过的数据的索引值，而非数据值。

入栈及出栈规则如下：

  1. 当栈为空时，入栈
  2. 当栈顶元素小于当前值时，当前值入栈
  3. 当栈顶元素不小于当前值时，栈顶元素出栈，此时计算当前出栈元素的高，所能围成的最大矩形。
  4. 再次比较栈顶元素与当前值的大小

面积计算规则为：出栈元素高度 * (当前值索引 - （出栈后，栈内top元素索引） - 1) ，如下示意图：

当遍历到index=4时，此时栈中保存着[1, 2, 3]，此时heights[4] < heights[3]，所以要出栈，计算以heights[3]所能围成的最大面积：(4 - 2 - 1) * heights[3]。

此时栈顶元素的值 heights[2] > heights[4]，所以要继续出栈，面积：(4 - 1 - 1) * heights[2]，注意处理边界情况，即当出栈之后栈为空时。

继续：

当遍历一遍之后，此时栈中还保存有一系列有序的元素，以这题为例，剩余结果如下：

因为是一个有序的列表，在其后的高度，都是高于之前的，这点要理解。

从头到尾遍历，所能围成的面积即为，当前高度 heights[index] * (当前索引到末尾元素的索引差)

经过以上计算方法，最后得到的最大值，即为所能围成的最大矩形面积。

代码实现：

Python实现，GitHub地址为：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c84.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def largestRectangleArea(heights):
    """
    :type heights: List[int]
    :rtype: int
    """
    arr = []
    ans = 0
    for index, item in enumerate(heights):

        if len(arr) == 0:
            arr.insert(0, index)
            continue

        if item > heights[arr[0]]:
            arr.insert(0, index)
        else:
            while heights[arr[0]] >= item:
                top = arr.pop(0)
                if len(arr) == 0:
                    temp = index * heights[top]
                else:
                    temp = (index - arr[0] - 1) * heights[top]

                if temp > ans:
                    ans = temp
                if len(arr) == 0:
                    break

            arr.insert(0, index)

    if len(arr) > 0:
        last = arr[0]

        while len(arr) > 0:
            top = arr.pop(0)

            if len(arr) > 0:
                temp = (last - arr[0]) * heights[top]
                if temp > ans:
                    ans = temp
            else:
                temp = (last + 1) * heights[top]
                if temp > ans:
                    ans = temp

    return ans