题解 | 求最大子矩阵的大小

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		row, _ := strconv.Atoi(scanner.Text())
		if row == 0 {
			break
		}

		scanner.Scan()
		col, _ := strconv.Atoi(scanner.Text())
		if col == 0 {
			break
		}
		arr := make([][]int, row)
		for i := 0; i < row; i++ {
			arr[i] = make([]int, col)
			for j := 0; j < col; j++ {
				scanner.Scan()
				arr[i][j], _ = strconv.Atoi(scanner.Text())
			}
		}
		fmt.Println(process(arr))
	}
}

func process(arr [][]int) int {
	if len(arr) == 0 {
		return 0
	}
	dp := make([]int, len(arr[0]))
	maxarea := 0
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			if arr[i][j] == 1 {
				dp[j] += 1
			} else {
				dp[j] = 0
			}
		}

		index := make([]int, 0, len(dp))
		n := len(dp)
	    // 左右边界，求最大面积，单调栈思路
		for k := 0; k <= n; k++ {
			h := 0
			if k < n {
				h = dp[k]
			}
			for len(index) > 0 && h < dp[index[len(index)-1]] {
				height := dp[index[len(index)-1]]
				index = index[:len(index)-1]
				width := k
				if len(index) > 0 {
					width = k - index[len(index)-1] - 1
				}
				maxarea = max(maxarea, height*width)
			}
			index = append(index, k)
		}

	}
	return maxarea
}

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