0085.最大矩形

https://leetcode.cn/problems/maximal-rectangle/

方法一：单调栈

时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，其中 m，n 表示 matrix 矩阵的长和宽。

func maximalRectangle(matrix [][]byte) int {
	ans, m, n := 0, len(matrix), len(matrix[0])
	maxArea := func(heights []int) int {
		ans, left, right, stack, n := 0, make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
		for i := 0; i < n; i++ {
			for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
				right[stack[len(stack)-1]], stack = i, stack[:len(stack)-1]
			}
			left[i] = -1
			if len(stack) > 0 {
				left[i] = stack[len(stack)-1]
			}
			stack = append(stack, i)
		}
		for _, v := range stack {
			right[v] = n
		}
		for i := 0; i < n; i++ {
			area := (right[i] - left[i] - 1) * heights[i]
			if area > ans {
				ans = area
			}
		}
		return ans
	}
	heights := make([]int, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				heights[j] += 1
			} else {
				heights[j] = 0
			}
		}
		area := maxArea(heights)
		if area > ans {
			ans = area
		}
	}
	return ans
}