day 52 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形

本题跟接雨水的思路是差不多的，不同的是接雨水找到的凹，这个找的是凸。因此是找到左右第一个比他小的值。因此单调栈中的顺序是从栈头到栈尾单调增。
需要注意的是，为了防止给定的元素是单调增或者单调减，所以需要在给定元素的头和尾两处加上两个0值。

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0)
    stack = append(stack, 0)
    new := make([]int, len(heights) + 2)
    new[0] = 0
    new[len(heights)+1] = 0
    for i := 1; i <= len(heights);i++{
        new[i] = heights[i-1]
    }
    res := 0
    for i := 1; i < len(new);i++{
        if new[i] > new[stack[len(stack)-1]]{
            stack = append(stack, i)
        }else if new[i] == new[stack[len(stack)-1]]{
            stack = stack[:len(stack)-1]
            stack = append(stack, i)
        }else{
            for len(stack) != 0 && new[i] < new[stack[len(stack)-1]]{
                h := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                if len(stack) != 0{
                    w := i - stack[len(stack)-1] - 1
                    res = max(res, w * new[h])
                }
            }
            stack = append(stack, i)
        }
    }
    return res
}
func max( a,b int)int{
    if a < b{
        return b
    }
    return a
}
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