leetcode84：Largest Rectangle in Histogram-蒲公英云

leetcode84：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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

求直方图中的最大矩形面积。

这里利用单调栈的方法，单调栈中保存heights的index，要始终保持单调栈中的index对应的高度heights是不递减的。

index从heights数组开始遍历，每次最大限度的将heights的index入栈（heights[index] heights[栈顶]），然后进行出栈操作。

一直出栈到heights[index] >= heights[栈顶]或者栈空为止，每个元素p出栈后，计算一下可能的最大面积，高度h是heights[p]；

宽度w是index - height[栈顶] - 1，面积就是h * w。注意宽度的计算，不能是index - height[p]，因为已经出栈的p和当前栈顶元素可能不是连续的，他们中间可能有更高的heights被出栈了。

另外注意栈空的情况，宽度就变成了index，栈空表明刚出栈的p的heights[p]是index前面最小的，所以宽度是index。

func largestRectangleArea(height []int) int {
    n := 0
    if n = len(height); n == 0 {
        return 0
    }
    ans := 0
    stack := make([]int, n)
    for i := 0; i < n; i++ {
        if isEmpty(stack) || height[top(stack)] <= height[i] {
            stack = append(stack, i) //这里入栈的是index，不是height[index]
            continue
        }
        for !isEmpty(stack) && height[top(stack)] > height[i] {
            pos := pop(stack)
            stack = stack[:len(stack) - 1]
            Height := height[pos]
            var Width int
            if isEmpty(stack) {
                Width = i
            } else {
                Width = i - top(stack) - 1
            }
            if ans < Height * Width {
                ans = Height * Width
            }
        }
        i--  //减一将当前的index入栈
    }
    fmt.Println("here")
    for !isEmpty(stack) {
        pos := pop(stack)
        stack = stack[:len(stack) - 1]
        Height := height[pos]
        var Width int
        if isEmpty(stack) {
            Width = n
        } else {
            Width = n - top(stack) - 1
        }
        if ans < Height * Width {
            ans = Height * Width
        }
    }
    return ans
}
func top(stack []int) int {
    return stack[len(stack) - 1]
}
func isEmpty(stack []int) bool {
    if len(stack) == 0 {
        return true
    }
    return false
}
func pop(stack []int) (int) {
    ret := stack[len(stack) - 1]
    return ret
}