84. Largest Rectangle in Histogram

    func largestRectangleArea(_ hei: [Int]) -> Int {
        var heights = hei
        heights.append(0)
        var res = 0
        var stackH = [Int]()
        var stackIndex = [Int]()
        //保持递增
        for (index, h) in heights.enumerated(){
            if stackH.count  == 0 || h > stackH.last! {
                stackH.append(h)
                stackIndex.append(index)
            }else {
                while stackH.count > 0 && h <= stackH.last! {
                    let lastH = stackH.removeLast()
                    stackIndex.removeLast()
                    let leftIndex = stackIndex.count > 0 ? stackIndex.last! : -1
                    res = max(res, lastH * (index - leftIndex - 1))
                }
                stackH.append(h)
                stackIndex.append(index)
            }

        }
        return res
    }
}