leetcode85 Maximal Rectangle
2024-09-03 07:00:53
思路:
分别按行拆分后将这一行之前的每列叠加起来,然后使用leetcode84https://www.cnblogs.com/wangyiming/p/9620942.html的思路计算。
实现:
#include <bits/stdc++.h>
using namespace std; class Solution
{
public:
int maximalRectangle(vector<vector<char>>& matrix)
{
int n = matrix.size(); if (n == ) return ;
int m = matrix[].size(); if (m == ) return ;
int ans = ;
vector<int> h(m, ), l(m, ), r(m, );
for (int i = ; i < n; i++)
{
for (int j = ; j < m; j++)
{
h[j] = (matrix[i][j] == '' ? : h[j] + );
}
stack<int> s;
for (int j = ; j < m; j++)
{
while (!s.empty() && h[s.top()] >= h[j]) s.pop();
l[j] = (s.empty() ? : s.top() + );
s.push(j);
}
while (!s.empty()) s.pop();
for (int j = m - ; j >= ; j--)
{
while (!s.empty() && h[s.top()] >= h[j]) s.pop();
r[j] = (s.empty() ? m - : s.top() - );
s.push(j);
}
for (int j = ; j < m; j++)
{
ans = max(ans, (r[j] - l[j] + ) * h[j]);
}
}
return ans;
}
};
int main()
{
char a[][] = {{'','','','',''},
{'','','','',''},
{'','','','',''},
{'','','','',''}};
// char a[][4] = {{'1','1','1','1'},
// {'1','1','1','1'},
// {'1','1','1','1'}};
vector<vector<char>> v;
for (int i = ; i < ; i++)
{
v.push_back(vector<char>(a[i], a[i] + ));
}
cout << Solution().maximalRectangle(v) << endl;
return ;
}
最新文章
- wp8 入门到精通 Utilities类 本地存储+异步
- csuoj 1511: 残缺的棋盘
- android 解决ScrollView嵌套ListView的问题,不能全屏,全屏不能显示下面控件
- mysql 任意连接
- JVM——垃圾收集算法
- erlang常用命令
- Linux epoll总结
- 【bootstrap】时间选择器datetimepicker和daterangepicker
- Telnet的开启及使用
- 【Idea】idea waiting until last debugger command completes
- Linux命令面试集
- Kali Linux2018 上安装open-vm-tools实现虚拟机交互
- 使用canvas实现一个圆球的触壁反弹
- MT【55】近零点
- kettle的系列教程
- [日常] Go语言圣经-GIF动画练习语法
- OpenERP 负载平衡
- 『ACM C++』 PTA 天梯赛练习集L1 | 042-43
- [USACO06DEC] Milk Patterns
- 0x05 MySQL 数据操作
热门文章
- Command line option syntax error. Type Command /? for Help.
- 共用体的定义和应用【C++】
- 9、IPA通路分析相关网页教程
- CodeForces 492A Vanya and Cubes
- 22. CTF综合靶机渗透(十五)
- Apple Swift中文入门教程【转发】
- 1.jQuery入口函数 与javaScript入口函数
- sed命令使用
- 使用配置类而不使用XML文件(代替bean.xml)对spring进行配置
- 求组合数 C(n,m)