題目及測試
package pid085;
/* 85. 最大矩形
給定一個僅包含 0 和 1 的二維二進制矩陣，找出隻包含 1 的最大矩形，并傳回其面積。
示例:
輸入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
輸出: 6
*/
import java.util.List;
public class main {
public static void main(String[] args) {
char[][] testTable = {{'1','0','1','0','0'},{'1','0','1','1','1'},
{'1','1','1','1','1'},{'1','0','0','1','0'}};
test(testTable);
}
private static void test(char[][] ito) {
Solution solution = new Solution();
int rtn;
long begin = System.currentTimeMillis();
for(char[] now:ito){
for(char nowc:now){
System.out.print(nowc+" ");
}
System.out.println();
}
System.out.println();
//開始時列印數組
rtn= solution.maximalRectangle(ito);//執行程式
long end = System.currentTimeMillis();
System.out.println("rtn=" );
System.out.print(rtn);
System.out.println();
System.out.println("耗時：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
自己沒想出來
解法1（别人的）
動态規劃 - 使用柱狀圖的優化暴力方法
我們可以以常數時間計算出在給定的坐标結束的矩形的最大寬度。我們可以通過記錄每一行中每一個方塊連續的“1”的數量來實作這一點。每周遊完一行，就更新該點的最大可能寬度。通過以下代碼即可實作。 row[i] = row[i - 1] + 1 if row[i] == '1'.
一旦我們知道了每個點對應的最大寬度，我們就可以線上性時間内計算出以該點為右下角的最大矩形。當我們周遊列時，可知從初始點到目前點矩形的最大寬度，就是我們遇到的每個最大寬度的最小值。
我們定義：
maxWidth=min(maxWidth,widthHere)
curArea=maxWidth∗(currentRow−originalRow+1)
maxArea=max(maxArea,curArea)
就是每次的面積=長*到這個點最大的寬，不斷計算最大的面積
對每個點重複這一過程，就可以得到全局最大。
注意，我們預計算最大寬度的方法事實上将輸入轉化成了一系列的柱狀圖，每一欄是一個新的柱狀圖。我們在針對每個柱狀圖計算最大面積。
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int maxarea = 0;
int[][] dp = new int[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if (matrix[i][j] == '1'){
// compute the maximum width and update dp with it
dp[i][j] = j == 0? 1 : dp[i][j-1] + 1;
int width = dp[i][j];
// compute the maximum area rectangle with a lower right corner at [i, j]
for(int k = i; k >= 0; k--){
width = Math.min(width, dp[k][j]);
maxarea = Math.max(maxarea, width * (i - k + 1));
}
}
}
} return maxarea;
}
}
解法2（别人的）
使用柱狀圖 - 棧
在上一方法中我們讨論了将輸入拆分成一系列的柱狀圖，每個柱狀圖代表一列的子結構。為了計算長方形的最大面積，我們僅僅需要計算每個柱狀圖中的最大面積并找到全局最大值（注意後面的解法對每一行而非列建立了柱狀圖，兩者思想一緻）。
class Solution {
// Get the maximum area in a histogram given its heights
public int leetcode84(int[] heights) {
Stack < Integer > stack = new Stack < > ();
stack.push(-1);
int maxarea = 0;
for (int i = 0; i < heights.length; ++i) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
stack.push(i);
}
while (stack.peek() != -1)
maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
return maxarea;
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int maxarea = 0;
int[] dp = new int[matrix[0].length];
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
// update the state of this row's histogram using the last row's histogram
// by keeping track of the number of consecutive ones
dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
}
// update maxarea with the maximum area from this row's histogram
maxarea = Math.max(maxarea, leetcode84(dp));
} return maxarea;
}
}
解法3（别人的）
想象一個算法，對于每個點我們會通過以下步驟計算一個矩形：
不斷向上方周遊，直到遇到“0”，以此找到矩形的最大高度。
向左右兩邊擴充，直到無法容納矩形最大高度。
例如，找到黃色點對應的矩形：
我們知道，最大矩形必為用這種方式建構的矩形之一。
給定一個最大矩形，其高為 h， 左邊界 l，右邊界 r，在矩形的底邊，區間 [l, r]内必然存在一點，其上連續1的個數（高度）<=h。若該點存在，則由于邊界内的高度必能容納h，以上述方法定義的矩形會向上延伸到高度h，再左右擴充到邊界 [l, r] ，于是該矩形就是最大矩形。
若不存在這樣的點，則由于[l, r]内所有的高度均大于h，可以通過延伸高度來生成更大的矩形，是以該矩形不可能最大。
綜上，對于每個點，隻需要計算h， l，和 r - 矩形的高，左邊界和右邊界。
使用動态規劃，我們可以線上性時間内用上一行每個點的 h，l，和 r 計算出下一行每個點的的h，l，和r。
給定一行 matrix[i]，我們通過定義三個數組height，left，和 right來記錄每個點的h，l，和 r。height[j] 對應matrix[i][j]的高，以此類推。
問題轉化為如何更新每個數組。
Height:
這個比較容易。 h 的定義是從該點出發連續的1的個數。
row[j] = row[j - 1] + 1 if row[j] == '1'
隻需要一點改動即可:
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
Left:
考慮哪些因素會導緻矩形左邊界的改變。由于目前行之上的全部0已經考慮在目前版本的left中，唯一能影響left就是在目前行遇到0。
是以我們可以定義:
new_left[j] = max(old_left[j], cur_left)
cur_left是我們遇到的最右邊的0的序号加1。當我們将矩形向左 “擴充” ，我們知道，不能超過該點，否則會遇到0。
Right:
我們可以沿用 left 的思路，定義:
new_right[j] = min(old_right[j], cur_right)
cur_right 是我們遇到的最左邊的0的序号。簡便起見，我們不把 cur_right 減去1 (就像我們給cur_left加上1那樣) ，這樣我們就可以用height[j] * (right[j] - left[j]) 而非height[j] * (right[j] + 1 - left[j])來計算矩形面積。
這意味着， 嚴格地說 ，矩形的底邊由半開半閉區間[l, r) 決定，而非閉區間 [l, r]，且 right比右邊界大1。盡管不這樣做算法也可以正确運作，但這樣會讓計算看起來更簡潔。
注意，為了正确的記錄 cur_right，我們需要從右向左疊代。是以，更新right時需要從右向左。
一旦left，right，和 height數組能夠正确更新，我們就隻需要計算每個矩形的面積。
由于我們知道矩形 j的邊界和高，可以簡單地用height[j] * (right[j] - left[j])來計算面積，若j的面積 大于max_area，則更新之。
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[] left = new int[n]; // initialize left as the leftmost boundary possible
int[] right = new int[n];
int[] height = new int[n];
Arrays.fill(right, n); // initialize right as the rightmost boundary possible
int maxarea = 0;
for(int i = 0; i < m; i++) {
int cur_left = 0, cur_right = n;
// update height
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
// update left
for(int j=0; j<n; j++) {
if(matrix[i][j]=='1') left[j]=Math.max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// update right
for(int j = n - 1; j >= 0; j--) {
if(matrix[i][j] == '1') right[j] = Math.min(right[j], cur_right);
else {right[j] = n; cur_right = j;}
}
// update area
for(int j = 0; j < n; j++) {
maxarea = Math.max(maxarea, (right[j] - left[j]) * height[j]);
}
}
return maxarea;
}
}