本文主要是介绍Java | Leetcode Java题解之第85题最大矩形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
题解:
class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length;if (m == 0) {return 0;}int n = matrix[0].length;int[][] left = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == '1') {left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int ret = 0;for (int j = 0; j < n; j++) { // 对于每一列,使用基于柱状图的方法int[] up = new int[m];int[] down = new int[m];Deque<Integer> stack = new LinkedList<Integer>();for (int i = 0; i < m; i++) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}up[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();for (int i = m - 1; i >= 0; i--) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}down[i] = stack.isEmpty() ? m : stack.peek();stack.push(i);}for (int i = 0; i < m; i++) {int height = down[i] - up[i] - 1;int area = height * left[i][j];ret = Math.max(ret, area);}}return ret;}
}
这篇关于Java | Leetcode Java题解之第85题最大矩形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!