最大矩形

type rect struct {
    width  int
    height int
}

func maximalRectangle(matrix [][]byte) int {
    ans := 0
    // 用 cols 长度定一个一个数组（沿用柱状图中最大的矩形的解题思路）
    // 因为题目保证 1 <= row, cols <= 200
    heights := make([]int, len(matrix[0]))
    // 遍历每行元素
    for _, raw := range matrix {
        for i, v := range raw {
            // 如果当前值为 0，类比柱状图中的 height[i] = 0
            // (就算此前累积了高度遇到当前的 0 也会断开，变得不连续)
            if v == '0' {
                heights[i] = 0
            } else { // 否则 height[i] 应该等于之前累积的高度再加上当前的 1
                heights[i]++
            }
        }
        ans = max(ans, largestRectangleArea(heights))
    }
    return ans
}

// largestRectangleArea leetcode84. 柱状图中最大的矩形解。
func largestRectangleArea(heights []int) int {
    ans := 0 
    // 构建单调递增栈，高的柱子遇到矮的柱子可以贡献自身高度
    stk := make([]*rect, 0, len(heights))
    // 在柱形图末尾补零，保证触发单调递增栈的出栈逻辑
    heights = append(heights, 0)
    for _, h := range heights {
        acculmatedWidth := 0 
        // 如果栈不空，并且无法构成递增（此时需要出栈栈顶）
        for len(stk) > 0 && stk[len(stk) - 1].height > h {
            // 取栈顶  
            top := stk[len(stk) - 1]
            // 累积宽度(高的柱子贡献了自己的宽度)
            acculmatedWidth += top.width
            // 计算最大值
            ans = max(ans, acculmatedWidth * top.height)
            // 出栈
            stk = stk[:len(stk) - 1]
        }
        // +1 加的是自身的宽度
        acculmatedWidth += 1
        // 入栈当前矩形
        // acculmatedWidth 中包含了如果无法构成单调增而出栈的柱子的宽度
        stk = append(stk, &rect{
            width:  acculmatedWidth,
            height: h,
        })
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}