[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