柱状图中最大的矩形

题目描述：

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

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

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

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

思路:‘

第一种解法，暴力，这道问题的暴力解法比「接雨水」那道题要其实好想得多：可以枚举以每个柱形为高度的最大矩形的面积。

具体来说就是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。（golang会超时）

第二种解法是哨兵加上单调栈，就是如果出现前一个和后一个都比这个数小，就说明这个数的最大面积已经算出来的，可以出局了

代码:

//第一种解法
func largestRectangleArea(heights []int) int {
    if len(heights)==0{
        return 0
    }
    var sum,max,i,j int
 
    for k,v :=range heights{
        for i = k-1;i>=0 && i<len(heights);i--{
            if heights[i]<heights[k]{
                break
            }
        }
        for j = k+1;j>=0 && j<len(heights);j++{
            if heights[j]<heights[k]{
                break
            }
        }
        sum = (j-i-1) *v
        fmt.Println(sum)
        if sum>max{
            max = sum
        }
    }
    return max
}

//解法二
func largestRectangleArea(heights []int) int {
	if len(heights) == 0 {
		return 0
	}
	stack := make([]int, 0, len(heights))
	heights = append(heights, -1)
	heights = append([]int{-1}, heights...)
	var maxsize int
	for i := 0; i < len(heights); i++ {
		for len(stack)>0&&heights[Peek(stack)] > heights[i] {
			stack, v := Pop(stack)
			if sum := (i - Peek(stack) - 1) * heights[v]; sum > maxsize {
				maxsize = sum
			}
		}
		stack = append(stack, i)
	}
	return maxsize
}
func Pop(stack []int) ([]int, int) {
	s := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	return stack, s
}
func Peek(stack []int) int {
	return stack[len(stack)-1]
}

代码效率：

执行用时：108 ms, 在所有 Go 提交中击败了49.43%的用户
内存消耗：9.1 MB, 在所有 Go 提交中击败了30.36%的用户