剑指 Offer II 040. 矩阵中最大的矩形
创始人
2025-05-29 07:55:54
0次

动态规划+栈

方法一仅动态规划：

  1. 仅求行的和，当位置本身未0时则，依次点为中心的矩阵皆为0，若当前位置为1，则该位置左侧值+1，这样我们可以求去以当前位置为右下角的矩阵的宽度

  1. 我们从该位置向上看，来寻找以该位置为右下角的最大矩阵面积，最合适的宽度*最合适的高度，算出面积与最大值做比较，选择最大值保存

class Solution {
public:int maximalRectangle(vector& matrix) {// 动态规划，如果当前位置是1，那么当前位置观看上和左的值// 自作向右遍历，自上向下遍历// 注意判断四个边界if(matrix.empty()){return 0;}int row = matrix.size();int col = matrix[0].size();vector> path(row+1,vector(col+1,0));int max_val = 0;for(int i=0;i=0&&path[k][j]!=0){// 计算目前矩阵的面积col_min = min(col_min,path[k][j]); // 可以获得目前矩阵的宽int h = i-k+1;    // 目前矩阵的高max_val = max(max_val,h*col_min);    // 计算面积与最大面积比较k--;}}else {if(matrix[i][j] == '0'){path[i][j] = 0;}else{path[i][j]=path[i][j-1]+1;}// 向上看寻找合适的矩阵int k = i;int col_min = 201;  // 用来标记列中的最小值while(k>=0&&path[k][j]!=0){// 计算目前矩阵的面积col_min = min(col_min,path[k][j]); // 可以获得目前矩阵的宽int h = i-k+1;    // 目前矩阵的高max_val = max(max_val,h*col_min);    // 计算面积与最大面积比较k--;}}cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：品荔枝吃粽子、看"龙超"让端午更有"岭南味儿"

下一篇：第二十章 opengl之高级OpenGL（高级数据）

相关内容

热门资讯

熵_相对熵_散度 1 信息量 意外越大，越不可能发生，概率就越小，信息量也就...
张家界旅游攻略最佳攻略：玩透张... 张家界旅游攻略最佳攻略：玩透张家界就看这篇！ 大家好！我是小李，刚从张家界回来，必须和大家分享我的...
暑假带娃玩转西北畅玩小团｜青甘... ✨**带娃畅玩西北，青甘环线轻松搞定！跟着阿洁出发，体验不一样的大美风光！**✨ 我这次暑假带着孩子...
想带父母去四川旅游6天5晚要多... 想带父母去四川旅游6天5晚要多少钱？带父母去四川旅游该怎么玩？看驴友怎么玩 四川，那片充满魅力和生机...
黄山提供一站式的咨询攻略！黄山... 黄山提供一站式的咨询攻略！黄山旅行社4日游尊享版多少钱？ 黄山，位于安徽省南部黄山市境内，它不仅仅是...
自驾一小时直达！在济南南部山区... 图源｜小红书：荒野之鹿 当山溪漫过脚踝卷走夏日的燥热，待篝火将吉他染成橙红，所有被城市折叠的自由都会...
市区藏绝美湿地公园！日落白鹭齐... 在城市的喧嚣中，总有一些地方像隐秘的宝石，静静等待着被发现。位于市区的一处湿地公园，便是这样一片令人...
第三届衡阳市旅游发展大会主题口... 第三届衡阳市旅游发展大会主题口号、形象标识（LOGO）评选结果公布 为全力办好第三届衡阳市旅游发展大...
潮汕三天两夜旅游多少钱，潮汕三... 潮汕地区，这片充满文化底蕴与独特魅力的土地，一直以来都是众多游客向往的旅游胜地。它不仅有着悠久的历史...
穹游自助租赁柜：以智能科技赋能...
枣庄市“鲁风运河”古城文化廊道...
人到山西好风光 青春“晋”行时... 5月27-28日，山西省文旅厅走进山东大学、中国石油大学（华东）开展进校园主题推介活动，吸引山东学子...
旅游小镇票务系统解决方案分享：... 宜良九乡旅游小镇，坐落于云南省昆明市宜良县，是一个令人心驰神往的旅游胜地。这里融合了丛林奇观、古人类...
原创 7... 近日，曾志伟和谭咏麟一起在日本旅行的消息吸引了众多网友的关注。大家纷纷羡慕他们几十年的深厚友谊，但鲜...
土耳其旅游促进和发展局连续第三... 5月27日，2025 ITB上海国际旅游交易博览会（ITB China）在上海世博展览馆盛大启幕。 ...
重庆多个水上乐园开浪！粽香里冲... 本周末 我们即将迎来端午节与儿童节的奇妙邂逅 跟节日一样让人期待的夏日限定快乐 —— 水上乐园🌊 ...
和姐妹去黄山旅游五天需要多少钱... 黄山，这座被誉为“天下第一奇山”的名山，以其奇松、怪石、云海、温泉四绝闻名于世。一直以来，它都是我心...
北京旅游五天四晚大概要多少钱？... 北京，这座古老与现代交织的城市，承载着千年的历史与文化。从宏伟壮观的故宫到繁华热闹的王府井，从静谧幽...
惠州市惠阳区淡水哪个桑拿酒店服... 在惠州市惠阳区淡水，桑拿酒店众多，每一家都宣称自己服务优质131。对于渴望在忙碌生活中寻得放松与享受...
渔湾景区打造非遗数字文旅新标杆 夜幕降临，连云港渔湾景区珍珠瀑布前，1600℃的铁水被击向夜空，瞬间化作漫天金色星雨。游客的惊叹声未...