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

PS：

使用單調棧方法求解(同84)

class Solution {

public int maximalRectangle(char[][] matrix) {

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;

int[] height = new int[matrix[0].length];

int globalmax = 0;

for (int i = 0; i < matrix.length; i++){

for (int j = 0; j < matrix[0].length; j++){

if (matrix[i][j] == '0') height[j] = 0;

else height[j]++;

}

globalmax = Math.max(globalmax, maxrow(height));

}

return globalmax;

}

public int maxrow(int[] height){

Stack st = new Stack<>();

int localmax = 0;

for (int i = 0; i <= height.length; i++){

int h = (i == height.length)? 0 : height[i];

while (!st.isEmpty() && height[st.peek()] >= h){

int maxheight = height[st.pop()];

int area = st.isEmpty()? i * maxheight : maxheight * (i - st.peek() -1);

localmax = Math.max(localmax, area);

}

st.push(i);

}

return localmax;

}

}

總結

以上是生活随笔為你收集整理的java 最大矩形_Java实现 LeetCode 85 最大矩形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。