Leetcode

LeetCode-最大長方形（JAVa）



Leetcode Maximal Rectangle Java



0と1で満たされた2Dバイナリ行列が与えられた場合、1のみを含む最大の長方形を見つけて、その面積を返します。
画像
説明：リファレンス LeetCode-ヒストグラムで最大の長方形（JAVA）
2次元配列の各行について、ヒストグラムを生成し、ヒストグラムで最大の長方形を見つけます。

class Solution { public int maximalRectangle(char[][] matrix) { int n = matrix.length if(n < 1) { return 0 } int m = matrix[0].length if(m < 1) { return 0 } int[] h = new int[m + 1] Stack<Integer> sts = new Stack<Integer>() int area = 0 for(int i = 0 i < n i++) { for(int j = 0 j < m j++) { if(matrix[i][j] == '0') { h[j] = 0 } else { h[j] += 1 } while(!sts.isEmpty() && h[sts.peek()] > h[j]){ int t = sts.pop() area = Math.max(area, h[t] * (sts.isEmpty() ? j : j - sts.peek() - 1)) } sts.push(j) } while(!sts.isEmpty()) { int t = sts.pop() area = Math.max(area, h[t] * (sts.isEmpty() ? m : m - sts.peek() - 1)) } } return area } }