首页 > 其他分享 >Leetcode 85. 最大矩形

Leetcode 85. 最大矩形

时间:2024-09-17 13:36:09浏览次数:10  
标签:rows matrix up stack down 矩形 85 Leetcode left

1.题目基本信息

1.1.题目描述

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

1.2.题目地址

https://leetcode.cn/problems/maximal-rectangle/description

2.解题方法

2.1.解题思路

动态规划+单调栈,可以参考Leetcode 84. 柱状图中最大的矩形

2.2.解题步骤

第一步,边界值判断

第二步,构建left矩阵,left[i][j]为matrix[i][j]处向左连续为1的个数(包括本身)

第三步,遍历每一列,使用最大矩阵的方法求每一列的各个元素能组成的最大矩阵的面积。对于每一列的遍历,目标是构建up和down两个数组,up[i]为j列的i处上面的第一个小于left[i][j]的行索引,down指i处下面的第一个小于left[i][j]的行索引,其中-1和rows相当于链表中的哑结点。中间使用单调栈工具,将与i处相邻且大于left[i][j]的元素pop掉,最后栈顶元素即为目标值。对于down,pop的元素对应的索引处的值一定是i,可以用反证法进行证明。构建每列的up和down后,遍历计算面积最大值即可

第四步,返回结果

3.解题代码

Python代码

class Solution:
    # 动态规划+单调栈
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        # 第一步,边界值判断
        if len(matrix)==0:
            return 0
        rows,cols=len(matrix),len(matrix[0])
        # 第二步,构建left矩阵,left[i][j]为matrix[i][j]处向左连续为1的个数(包括本身)
        left=[[0]*cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j]=='1':
                    left[i][j]=left[i][j-1]+1 if j!=0 else 1
        # print("left",left)
        # 第三步,遍历每一列,使用最大矩阵的方法求每一列的各个元素能组成的最大矩阵的面积。对于每一列的遍历,目标是构建up和down两个数组,up[i]为j列的i处上面的第一个小于left[i][j]的行索引,down指i处下面的第一个小于left[i][j]的行索引,其中-1和rows相当于链表中的哑结点。中间使用单调栈工具,将与i处相邻且大于left[i][j]的元素pop掉,最后栈顶元素即为目标值。对于down,pop的元素对应的索引处的值一定是i,可以用反证法进行证明。构建每列的up和down后,遍历计算面积最大值即可。
        result=0
        for j in range(cols):
            # up[i]为j列的i处上面的第一个小于left[i][j]的行索引;down指i处下面的第一个小于left[i][j]的行索引;其中-1和rows相当于链表中的哑结点
            up,down=[-1]*rows,[rows]*rows
            stack=[]
            for i in range(rows):
                while stack and stack[-1][0]>=left[i][j]:
                    item=stack.pop()
                    down[item[1]]=i
                if stack:
                    up[i]=stack[-1][1]
                stack.append((left[i][j],i))
            # print(up,down)
            for i in range(rows):
                result=max(result,(down[i]-up[i]-1)*left[i][j])
        # print(result)
        # 第四步,返回结果
        return result

C++代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0){
            return 0;
        }
        int rows=matrix.size(),cols=matrix[0].size();
        vector<vector<int>> left(rows,vector<int>(cols,0));
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j!=0 ? left[i][j-1]+1 : 1);
                }
            }
        }
        int result=0;
        for(int j=0;j<cols;++j){
            vector<int> up(rows,-1);
            vector<int> down(rows,rows);
            stack<pair<int,int>> stk;
            for(int i=0;i<rows;++i){
                while(!stk.empty() && stk.top().first>=left[i][j]){
                    auto item=stk.top();stk.pop();
                    down[item.second]=i;
                }
                if(!stk.empty()){
                    up[i]=stk.top().second;
                }
                stk.emplace(left[i][j],i);
            }
            for(int i=0;i<rows;++i){
                result=max(result,(down[i]-up[i]-1)*left[i][j]);
            }
        }
        return result;
    }
};

4.执行结果

在这里插入图片描述

标签:rows,matrix,up,stack,down,矩形,85,Leetcode,left
From: https://www.cnblogs.com/geek0070/p/18417105

相关文章

  • Leetcode 297. 二叉树的序列化与反序列化
    1.题目基本信息1.1.题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序......
  • Leetcode 952. 按公因数计算最大组件大小
    1.题目基本信息1.1.题目描述给定一个由不同正整数的组成的非空数组nums,考虑下面的图:有nums.length个节点,按从nums[0]到nums[nums.length-1]标记;只有当nums[i]和nums[j]共用一个大于1的公因数时,nums[i]和nums[j]之间才有一条边。返回图中最大连通组件的大小......
  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目:给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步,初始化快指针为head,慢指针指向一个哑结点,哑结点......
  • 【数据分享】1985-2023年30米CLCD土地覆盖栅格数据分享
    1.数据来源​CLCD反映了中国快速的城市化进程和一系列生态工程,揭示了气候变化条件下人为对LC的影响,其在全球变化研究中具有潜在应用价值。2021年7月,武汉大学杨杰、黄昕两位教授共同撰写题为《30mannuallandcoveranditsdynamicsinChinafrom1990to2019》的研究论......
  • Leetcode 2183. 统计可以被 K 整除的下标对数目
    1.题目基本信息1.1.题目描述给你一个下标从0开始、长度为n的整数数组nums和一个整数k,返回满足下述条件的下标对(i,j)的数目:0<=i<j<=n-1且nums[i]*nums[j]能被k整除。1.2.题目地址https://leetcode.cn/problems/count-array-pairs-divisible-by-k......
  • Leetcode—815. 公交路线【困难】(unordered_map+queue)
    2024每日刷题(163)Leetcode—815.公交路线bfs实现代码classSolution{public:intnumBusesToDestination(vector<vector<int>>&routes,intsource,inttarget){if(source==target){return0;}unordered_map<......
  • 教育部等十八部门关于加强新时代中小学科学教育工作的意见 20240917_085127
    原文教育部等十八部门关于加强新时代中小学科学教育工作的意见_国务院部门文件_中国政府网https://www.gov.cn/zhengce/zhengceku/202305/content_6883615.htm概述教育部等十八部门联合发布此意见,强调要加强科学教育,推动校内校外融合,规范科技类校外培训。这一政策为少儿编程教......
  • Java LeetCode每日一题
            1184.公交站间的距离    需求:        环形公交路线上有n个站,按次序从0到n-1进行编号。我们已知每一对相邻公交站之间的距离,distance[i]表示编号为i的车站和编号为(i+1)%n的车站之间的距离。        环线上的公交......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树,可知,如果中间节点是p和q的公共节点,那个中间节点的数值一定在[p,q]区间因此,从根节点往下搜索,遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • LeetCode题集-4 - 寻找两个有序数组的中位数,图文并茂,六种解法,万字讲解
    题目:给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log(m+n))。作为目前遇到的第一个困难级别题目,我感觉这题还是挺难的,研究了三天总算研究明白了,下面就给大家分享一下这题的几种解法,请......