Q：給出一個只包含0和1的二維矩陣，找出最大的全部元素都是1的長方形區(qū)域，返回該區(qū)域的面積。

A：

這個題感覺蠻巧妙的。

如果這個點為‘1’，先計算當前行的最大寬度，這說明最大寬度左邊的都是保證可以是矩形的。然后往上看，用最小的寬度和當前的高度計算最大的矩形。

看圖：

代碼：

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') {

//先計算最大寬度

if (j == 0) {

dp[i][j] = 1;

} else {

dp[i][j] = dp[i][j - 1] + 1;

}

int width = dp[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;

}

同理，高度也可以這么做。

另一種就是參考計算直方圖中最大矩形的面積

算法有了，就是求出每一層的 heights[] 然后傳給上一題的函數(shù)就可以了。

代碼：

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++) {

if (matrix[i][j] == '1') {

dp[j] = dp[j] + 1;

} else {

dp[j] = 0;

}

}

int area = maxRec(dp);

maxArea = Math.max(maxArea, area);

}

return maxArea;

}

private int maxRec(int[] heights) {

Stack 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;

}

總結(jié)

以上是生活随笔為你收集整理的leetcode最大矩形_LeetCode——最大矩形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。