Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Return 4.
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int max = 0; int[] height = new int[matrix[0].length]; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1; } max = Math.max(help(height), max); } return max; } private int help(int[] height) { // TODO Auto-generated method stub if (height == null || height.length == 0) { return 0; } int max = 0; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] <= height[stack.peek()]) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int cur = (i - k - 1) * height[j]; max = Math.max(max, cur); } stack.push(i); } while (!stack.isEmpty()) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int cur = (height.length - k - 1) * height[j]; max = Math.max(max, cur); } return max; } }
相关推荐
Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number ...
数据挖掘相关内容Redundancy-Aware Maximal Cliques,关于最大派系
The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs, thus providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that moves among ...
maximal square. Use dynamic programming. use just O(n) space. The extra space equals matrix col length. majority element ii . 使用 "摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、...
关于论文MaPle A Fast Algorithm for Maximal Pattern-based Clustering∗的翻译
2017 A Maximal Clique Based Multiobjective Evolutionary algorithm for overlapping community detection 论文PPT讲解
关于最大流网络算法的一些介绍,是外国文献,最大网络流的应用
Maximal Beasts
韩国人写的流数据分析SCI论文,2013年发表
纳米尺寸效应新应用:单键比热,强度,及应变极限,孙长庆,,Specific heat, strength, and maximal strain of atomic bond in an impurity-free monatomic chain.
非齐次分数次 Schr,张军勇,郑继强,本文考虑如下极大不等式$$ ig|sup_{0<t<1}|e^{itsqrt{1+(-Delta)^ lpha}}f(x)| ig|_{L^2(B(0,1))}leqC|f|_{H^s(mathbb R^d)},quad orall~fin H^s(mathbb R^d),quad ...
A new maximal-margin spherical-structured multi-class support vector machine Pei-Yi Hao · Jung-Hsien Chiang · Yen-Hsiu Lin Published online: 18 October 2007 © Springer Science+Business Media, LLC ...
一篇流数据分析方面的经典SCI论文,2013年发表的
Interactive image segmentation by maximal similarity based region merging
1.解压文件。运行Matlab,在Matlab中打开.../minepy/matlab/(当前文件夹为matlab); 2.在command window(命令行窗口)中输入:mex mine_mex.c ../libmine/mine.c; 3.测试代码: x = linspace(0, 1, 1001);...
图论资料,仅供学习使用,方便自己平时学习资料查阅,日常讲义积累,请勿用作商业用途,On Sparse Maximal 2-Planar Graphs
We propose a self-stabilizing algorithm for computing a maximal matching in an anony- mous network. The complexity is O(n2) moves with high probability, under the ad- versarial distributed daemon. ...
实现了区域合并的图像分割的经典方法,是Interactive Image Segmentation by Maximal Similarity based Region Merging 论文的源码,可以好好研究
这个文档的质量相当高,不过是纯英文的,但是,我保证你看过之后,肯定会认为这个文档写得实在太好了。