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