題目

給你一個二進位制矩陣 matrix ，它的大小為 m x n ，你可以將 matrix 中的 列 按任意順序重新排列。

請你返回最優方案下將 matrix 重新排列後，全是 1 的子矩陣面積。

示例 1：輸入：matrix = [[0,0,1],[1,1,1],[1,0,1]] 輸出：4

解釋：你可以按照上圖方式重新排列矩陣的每一列。

最大的全 1 子矩陣是上圖中加粗的部分，面積為 4 。

示例 2：輸入：matrix = [[1,0,1,0,1]] 輸出：3

解釋：你可以按照上圖方式重新排列矩陣的每一列。

最大的全 1 子矩陣是上圖中加粗的部分，面積為 3 。

示例 3：輸入：matrix = [[1,1,0],[1,0,1]] 輸出：2

解釋：由於你只能整列整列重新排布，所以沒有比面積為 2 更大的全 1 子矩形。

示例 4：輸入：matrix = [[0,0],[0,0]] 輸出：0

解釋：由於矩陣中沒有 1 ，沒有任何全 1 的子矩陣，所以面積為 0 。

提示：m == matrix.length

n == matrix[i].length

1 <= m * n <= 105

matrix[i][j] 要麼是 0 ，要麼是 1 。

解題思路分析

1、遍歷；時間複雜度O(n^2)，空間複雜度O(1)

func largestSubmatrix(matrix [][]int) int {	n, m := len(matrix), len(matrix[0])	for i := 1; i < n; i++ {		for j := 0; j < m; j++ {			if matrix[i][j] == 1 { // 統計以該行為基連續1的個數				matrix[i][j] = matrix[i][j] + matrix[i-1][j]			}		}	}	res := 0	for i := 0; i < n; i++ {		sort.Ints(matrix[i])		for j := m - 1; j >= 0; j-- {			height := matrix[i][j] // 高度有序，右邊最高=>高度取決於左邊			width := m - j			if height*width > res {				res = height * width			}		}	}	return res}

總結

Medium題目，先計算以每行為基的上方連續1的個數，然後排序計算面積即可