LeetCode-热题100：84. 柱状图中最大的矩形

题目描述

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

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

示例 1:

输入： heights = [2,1,5,6,2,3]
输出： 10
解释： 最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=10⁵
• 0 <= heights[i] <= 10⁴

代码及注释

func largestRectangleArea(heights []int) int {
    res := 0
    length := len(heights)
    stack := make([]int, 0)  // 单调栈，用于存放直方图的索引
    left, right := make([]int, length), make([]int, length)  // 分别用于存放每个直方图的左边界和右边界

    // 计算每个直方图的左边界
    for i := 0; i < length; i++ {
        // 当当前直方图的高度小于栈顶直方图的高度时，出栈
        for len(stack) > 0 && heights[stack[len(stack) - 1]] >= heights[i] {
            stack = stack[:len(stack) - 1]
        }
        // 如果栈为空，表示当前直方图左边界为-1
        if len(stack) == 0 {
            left[i] = -1
        } else {
            // 否则，当前直方图的左边界为栈顶直方图的索引
            left[i] = stack[len(stack) - 1]
        }
        stack = append(stack, i)  // 当前直方图入栈
    }

    // 清空栈，重新使用
    stack = []int{}

    // 计算每个直方图的右边界
    for i := length - 1; i >= 0; i-- {
        // 当当前直方图的高度小于栈顶直方图的高度时，出栈
        for len(stack) > 0 && heights[stack[len(stack) - 1]] >= heights[i] {
            stack = stack[:len(stack) - 1]
        }
        // 如果栈为空，表示当前直方图右边界为n（n为直方图的总数）
        if len(stack) == 0 {
            right[i] = length
        } else {
            // 否则，当前直方图的右边界为栈顶直方图的索引
            right[i] = stack[len(stack) - 1]
        }
        stack = append(stack, i)  // 当前直方图入栈
    }

    // 计算最大矩形面积
    for i := 0; i < length; i++ {
        res = max(res, heights[i] * (right[i] - left[i] - 1))
    }
    return res
}

// 辅助函数，返回两个整数中的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
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
47
48
49
50
51
52
53
54
55

代码解释

1. 初始化:

   • 初始化一个单调栈 stack，用于存放直方图的索引。
   • 初始化两个数组 left 和 right，分别用于存放每个直方图的左边界和右边界。

2. 计算左边界:

   • 遍历数组 heights，对于每一个直方图：
     • 当当前直方图的高度小于栈顶直方图的高度时，出栈。
     • 如果栈为空，表示当前直方图左边界为-1。
     • 否则，当前直方图的左边界为栈顶直方图的索引。
     • 当前直方图入栈。

3. 计算右边界:

   • 遍历数组 heights（从后向前），对于每一个直方图：
     • 当当前直方图的高度小于栈顶直方图的高度时，出栈。
     • 如果栈为空，表示当前直方图右边界为n（n为直方图的总数）。
     • 否则，当前直方图的右边界为栈顶直方图的索引。
     • 当前直方图入栈。

4. 计算最大矩形面积:

   • 对于每一个直方图，计算其面积，并更新最大面积。

这个算法的时间复杂度是O(n)，其中n是直方图的长度。在每次迭代中都排除了一部分直方图，直到找到最大矩形面积或者遍历完整个直方图。