Description

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

给出一个直方图，求最大矩形面积。

Solution

首先假设直方图是升序的，比如：1, 3, 5, 6, 7

那么需要比较的面积有：1*5，3 * 4，5*3，6*2，7*1。

计算公式为：$ S(i) = height[i] * (length-i) $

所以最大面积：$ \max_{i=0}^n{S(i)} $

那遇到无序的数组怎么办呢？

根据提示可以是用栈，目的是用于构造升序数组：

假设当前高度为h：

  1. 如果升序则直接入栈
  2. 遇到降序，将栈中所有比h高的都利用公式计算出面积，然后降低它们的高度至h，使数组重新有序

例如数组1, 3, 4, 2, 3：

^
|   0
|  00 0
|  0000
| 00000
.------->

首先：1，3，4 都是升序，依次入栈（下标入栈）：
^
|   0       stack:
|  00           [2]
|  00           [1]
| 000           [0]
.------->

遇到：2，不符合升序，计算前面 3 和 4 的面积分别为：S(1)=3*2，S(2)=4*1
然后降低高度至 2
^
|           stack:  将 4 的下标出栈，保留 3 的下标（因为 3 所在位置是新高度的起点）
|
|  000          [1]
| 0000          [0]
.------->

遇到：3，符合升序，直接入栈
^
|           stack:
|     0         [4]
|  0000         [1]
| 00000         [0]
.------->

最后仍需要计算的面积有：S(0)=1*5，S(1)=2*4，S(4)=3*1

所以最大面积为 8

 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

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0)
    lenStack := len(stack)
    max := 0

    // 追加一个 -1，用于最后清空栈
    heights = append(heights, -1)

    for i := 0; i < len(heights); i++ {
        h := heights[i]

        if lenStack > 0 && h < heights[stack[lenStack-1]] {
            // 如果前面更高，将更高的都出栈
            // 同时计算面积，然后降低它们的高度（形成新的“有序”）
            for {
                idx := stack[lenStack-1]
                // 计算面积
                max = maxInt(max, heights[idx]*(i-idx))
                // 降低高度
                heights[idx] = h

                lenStack-- // 假出栈
                if lenStack == 0 || h > heights[stack[lenStack-1]] {
                    // 最后一个，保留在栈中作为新高度的起点
                    lenStack++
                    break
                }
                stack = stack[:lenStack]
            }
        } else /* 这个判断可有可无 if lenStack == 0 || h > heights[stack[lenStack-1]] */ {
            // 将当前索引入栈
            stack = append(stack, i)
            lenStack++
        }
    }

    return max
}

Similar Problem