在哪给人做网站,网站建设有钱赚吗,网站config配置教程,宣传页模板最大矩形
难度#xff1a;困难
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例1
输入#xff1a;matrix [[1,0,1,0,困难
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。
示例1
输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出6示例2
输入matrix []
输出0示例3
输入matrix [[0]]
输出0示例4
输入matrix [[1]]
输出1示例5
输入matrix [[0,0]]
输出0题解
是0084的进阶可以将它升维转换为二维数组具体如下 比如matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 可以转换为
4 0 3 0 0
3 0 2 3 2
2 1 1 2 1
1 0 0 1 0即将需要讨论的内容缩小将本来需要讨论的纵坐标转化为每一行的高之后就可以根据0084的算法来对每一行的内容都取最大面积之后对结果进行对比最大的数即为结果
想法代码
class Solution
{public static void Main(String[] args){char[][] matrix {new[] { 1, 0, 1, 0, 0 },new[] { 1, 0, 1, 1, 1 },new[] { 1, 1, 1, 1, 1 },new[] { 1, 0, 0, 1, 0 }};Solution solution new Solution();int ans solution.MaximalRectangle(matrix);Console.WriteLine(ans);}public int MaximalRectangle(char[][] matrix){int maxArea 0;int rows matrix.Length;int cols matrix[0].Length;int[] heights new int[cols];for (int i 0; i rows; i){for (int j 0; j cols; j){if (matrix[i][j] 0){heights[j] 0;}else{heights[j];}}maxArea Math.Max(maxArea, GetMaxArea(heights));}return maxArea;}public int GetMaxArea(int[] heights){int[] left new int[heights.Length];int[] right new int[heights.Length];Array.Fill(left, -1);Array.Fill(right, heights.Length);Stackint stack new Stackint();for (int i 0; i heights.Length; i){int height heights[i];while (stack.Count 0 heights[stack.Peek()] height){right[stack.Pop()] i;}if (stack.Count 0){left[i] stack.Peek();}stack.Push(i);}int ans 0;for (int i 0; i heights.Length; i){ans Math.Max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans;}
}
