思路:

分别按行拆分后将这一行之前的每列叠加起来,然后使用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 ;
}

最新文章

  1. wp8 入门到精通 Utilities类 本地存储+异步
  2. csuoj 1511: 残缺的棋盘
  3. android 解决ScrollView嵌套ListView的问题,不能全屏,全屏不能显示下面控件
  4. mysql 任意连接
  5. JVM——垃圾收集算法
  6. erlang常用命令
  7. Linux epoll总结
  8. 【bootstrap】时间选择器datetimepicker和daterangepicker
  9. Telnet的开启及使用
  10. 【Idea】idea waiting until last debugger command completes
  11. Linux命令面试集
  12. Kali Linux2018 上安装open-vm-tools实现虚拟机交互
  13. 使用canvas实现一个圆球的触壁反弹
  14. MT【55】近零点
  15. kettle的系列教程
  16. [日常] Go语言圣经-GIF动画练习语法
  17. OpenERP 负载平衡
  18. 『ACM C++』 PTA 天梯赛练习集L1 | 042-43
  19. [USACO06DEC] Milk Patterns
  20. 0x05 MySQL 数据操作

热门文章

  1. Command line option syntax error. Type Command /? for Help.
  2. 共用体的定义和应用【C++】
  3. 9、IPA通路分析相关网页教程
  4. CodeForces 492A Vanya and Cubes
  5. 22. CTF综合靶机渗透(十五)
  6. Apple Swift中文入门教程【转发】
  7. 1.jQuery入口函数 与javaScript入口函数
  8. sed命令使用
  9. 使用配置类而不使用XML文件(代替bean.xml)对spring进行配置
  10. 求组合数 C(n,m)