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

leetcode85. 最大矩形

时间:2024-02-02 11:14:19浏览次数:32  
标签:size 最大 int leetcode85 ans 矩形 dp matrix

85. 最大矩形 - 力扣(LeetCode)

参考dp求最大字串和的思想,将一维dp转化为二维的形式,将当前列的和当成一维的数进行dp即可。这题和求最大子矩阵和的dp思路一样。

 1 class Solution {
 2 public:
 3     int maximalRectangle(vector<vector<char>>& matrix) {
 4         int n = matrix.size();
 5         int m = matrix[0].size();
 6 
 7         int a[n+5][m+5];
 8 
 9         for(int i=0;i<m;i++){
10             for(int j=0;j<n;j++){
11                 a[j][i]=matrix[j][i]-'0';
12                 if(j>0)a[j][i]+=a[j-1][i];
13             }
14         }
15 
16         int ans=0;
17 
18         for(int i=0;i<n;i++){
19             for(int j=i;j<n;j++){
20 
21                 int b[m+5];
22 
23 
24                 for(int k=0;k<m;k++){
25                     if(i>0)b[k]=a[j][k]-a[i-1][k];
26                     else b[k]=a[j][k];
27 
28                     if(b[k]!=j-i+1)b[k]=0;
29                     else b[k]=1;
30 
31                     if(b[k]>0&&k>0){
32                         if(b[k-1]>0)b[k]+=b[k-1];
33                     }
34                     if(b[k])ans=max(ans,(j-i+1)*b[k]);
35                 }
36                 
37 
38             }
39         }
40         return ans;
41     }
42 };

 

 

       

标签:size,最大,int,leetcode85,ans,矩形,dp,matrix
From: https://www.cnblogs.com/ccsu-kid/p/18002779

相关文章

  • SQL PARTITION BY 语句把一张表分组后的最大值或最小值插入另一张表里
    1.例子见前一章,目的是有分组的,只显示OrderAmount最高的(即每组只显示一列) 2.再建一个表来存储CREATETABLE[dbo].[MaxOrders]([orderid][int]NULL,[Orderdate][date]NULL,[CustomerName][varchar](100)NULL,[Customercity][varchar](100)NULL,......
  • 上下界 可行/最大/最小 网络流/费用流(有/无源汇)
    对网络的定义进行扩展,我们可以得出一堆奇奇怪怪的网络。上下界令\(Max_e\)为边\(e\)的流量上界,\(Min_e\)为边\(e\)的流量下界,一条边的流量\(f_e\)要满足\(Min_e\lef_e\leMax_e\),除此之外和普通网络流定义相同,可以发现,普通的网络就是下界为\(0\)的网络。无源汇......
  • Linux中 awk命令输出一列多个类别中 每个类别中最大的项
     001、(base)[b20223040323@admin1test]$lsa.txt(base)[b20223040323@admin1test]$cata.txt##测试数据a88a76b88c10b777c200a87c150a34b25a66##输出第一列中每一类别中值最大的项(base)[b20223040......
  • 最大连续1的个数
    485.MaxConsecutiveOnes(Easy)给定一个二进制数组,计算其中最大连续1的个数。示例1:输入:[1,1,0,1,1,1]输出:3解释:开头的两位和最后的三位都是连续1,所以最大连续1的个数是3.注意:输入的数组只包含0和1。输入数组的长度是正整数,且不超过10,000。publicint......
  • P1029 最大公约数和最小公倍数问题
    321上题目链接:P1029[NOIP2001普及组]最大公约数和最小公倍数问题本小蒟蒻的原始思路就是枚举所有范围内的数,分别求出他们的最大公约数和最小公倍数,再看是否满足题意。于是就有了以下一言难尽的东西(;′⌒`)↓#include<stdio.h>intmain(){intx,y,count;sc......
  • 网络流最大流
    最大流问题有向图G中,有两个特殊的点,源点和汇点,每条边有指定的容量,求S到T的最大流。就像从源点放水,水量无穷大,汇点的水量是多少?定义c为容量,f为流量流量守恒\(f(x,y)\leqc(x,y)\)容量性质\(\sumf(u,x)=\sumf(x,u)\)斜对称性\(f(x,y)=-f(y,x)\)容量网络,流量网络......
  • 代码随想录 day34 K 次取反后最大化的数组和 加油站 分发糖果
    K次取反后最大化的数组和按照元素的绝对值大小进行排序把绝对值大的且小于0的取反如果还能取反那么奇数次的话就把绝对值小的取反偶数次不用管加油站首先如果总油量小于总消耗是一定不能跑完的这里的思路是如果[0,i]区间不能油量小于消耗那么就尝试从下一个i+1......
  • P5369 [PKUSC2018] 最大前缀和
    [PKUSC2018]最大前缀和LuoguP5369题目描述小C是一个算法竞赛爱好者,有一天小C遇到了一个非常难的问题:求一个序列的最大子段和。但是小C并不会做这个题,于是小C决定把序列随机打乱,然后取序列的最大前缀和作为答案。小C是一个非常有自知之明的人,他知道自己的算法完全......
  • [office] MAX、MIN与IF结合,统计众多部门中同一部门数据最大值与最小值
    一位做电商数据分析的朋友说,他要对所管理的六个仓库的销售额进行对比统计,统计出每个仓库的最高与最低销售额。他有几万行的数据,简化到下面几行,以方便清楚统计公式。公式实现在E2单元格输入公式:“=MAX(IF($A$2:$A$16=D2,$B$2:$B$16))”,按“Ctrl+Shift+Enter”结束,向下填充,即可计算出......
  • STA(静态时序分析) 详解:如何计算最大时钟频率,以及判断电路是否出现时钟违例(timing viola
    1.什么是STA?     STA(静态时序分析)是时序验证的一种方法,用于计算和分析电路是否满足时序约束的要求。 2.为什么需要STA?    电路能否正常工作,其本质上是受最长逻辑通路(即关键路径)的限制,以及受芯片中存储器件的物理约束或工作环境的影响。    为了保......