85. Maximal Rectangle

逃离我推掉我的手 2021-12-22 06:53 204阅读 0赞

class Solution {
        public int maximalRectangle(char[][] matrix) {
            if(matrix.length==0||matrix[0].length==0)
                return 0;
            int[] heights=new int[matrix[0].length];
            int maxArea=0;
            Stack<Integer> stack=new Stack<Integer>();
            for(int i=0;i<matrix.length;i++)
            {
                for(int j=0;j<matrix[0].length;j++)
                    heights[j]=matrix[i][j]=='0'?0:heights[j]+1;
                
                stack.clear();
                for(int j=0;j<=matrix[0].length;j++)
                {
                    int h=j==matrix[0].length?0:heights[j];
                    if(stack.isEmpty()||heights[stack.peek()]<=h)
                        stack.push(j);
                    else
                    {
                        int idx=stack.pop();
                        int width=stack.isEmpty()?j:j-stack.peek()-1;
                        maxArea=Math.max(maxArea, heights[idx]*width);
                        j--;
                    }
                }
            }
            return maxArea;
        }
    }

转载于:https://www.cnblogs.com/asuran/p/7604779.html

发表评论取消回复

表情：

评论列表（有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 85. Maximal Rectangle | 85. 最大矩形（单调栈）

题目 [https://leetcode.com/problems/maximal-rectangle/][https_leetcode.com_problems_max

男娘i/ 2022年09月11日 11:23/ 0 赞/ 97 阅读

相关 leetcode 85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing

迈不过友情╰/ 2022年08月21日 03:14/ 0 赞/ 160 阅读

相关 LeetCode85——Maximal Rectangle

LeetCode85——Maximal Rectangle 初看这道题有点不知所措，但是其实是`LeetCode84——Largest Rectangle in Hist

痛定思痛。/ 2022年08月20日 04:11/ 0 赞/ 75 阅读

相关 leetcode:85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing

Dear 丶/ 2022年07月15日 23:56/ 0 赞/ 146 阅读

相关 [leetcode] 85. Maximal Rectangle

85. Maximal Rectangle Given a 2D binary matrix filled with 0’s and 1’s, find the large

古城微笑少年丶/ 2022年06月13日 03:27/ 0 赞/ 185 阅读

相关 leetcode85：Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing

柔光的暖阳◎/ 2022年05月11日 14:38/ 0 赞/ 195 阅读

相关 85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing

爱被打了一巴掌/ 2022年05月06日 04:28/ 0 赞/ 211 阅读

相关 LeetCode：85. Maximal Rectangle（最大的矩形）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

Bertha 。/ 2022年04月10日 02:26/ 0 赞/ 249 阅读

相关【Leetcode】85. Maximal Rectangle（求最大矩形）（动态规划）

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing

一时失言乱红尘/ 2022年02月23日 09:50/ 0 赞/ 328 阅读

相关 85. Maximal Rectangle

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

逃离我推掉我的手/ 2021年12月22日 06:53/ 0 赞/ 205 阅读