[LeetCode] 85. Maximal Rectangle

轉自LeetCode

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

 

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 0 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

Solution

思考了很久，除了暴力法之外沒想到好的解法

看了資料，覺得有個想法滿不錯的

首先，先計算每個 row 的連續 1，也就是找高度為 1 的 rect

然後，再往上找可以形成更大 rect 的位置

當在往上找的時候，寬度必須用比較小的那一個

舉例

0 1

1 1

水平矩形的計算結果為

0 1

1 2

往上找可以形成更大 rect 時，在 2 那個位置往上找的時候

寬必須是 1 = min(1, 2)，可以回頭看一開始的 value 來比對

kotlin

	class Solution {
	fun maximalRectangle(matrix: Array<CharArray>): Int {
	return if (matrix.isEmpty() || matrix[0].isEmpty()) {
	0
	} else {
	val rectMap = Array(matrix.size) { IntArray(matrix[0].size) {0}}
	//>> find largest rectange horizontally
	//>> ie. height = 1
	for(i in matrix.indices) {
	for(j in matrix[0].indices) {
	if(matrix[i][j] == '1') {
	if(j == 0) {
	rectMap[i][j] = 1
	} else {
	rectMap[i][j] = rectMap[i][j-1] + 1
	}
	}
	}
	}
	//>> find largest rectange vertically
	var ans = 0
	var currValue = 0
	for(i in 0 until matrix.size) {
	for(j in matrix[0].indices) {
	currValue = rectMap[i][j]
	ans = Math.max(ans, currValue)
	for(k in i-1 downTo 0) {
	currValue = Math.min(currValue, rectMap[k][j])
	ans = Math.max(ans, currValue * (i - k + 1))
	}
	}
	}
	return ans
	}
	}
	}

view raw maximal_rectangle.kt hosted with ❤ by GitHub