leetcode84：Largest Rectangle in Histogram

朴灿烈づ我的快乐病毒、 2022-05-11 14:36 145阅读 0赞

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.

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

![histogram_area.png][]  
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
    }

[histogram.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram.png
[histogram_area.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png