微信小程序 建网站 百度搜索优化 unity 智慧树 二代征信 网络营销推广 datagrid vue前端开发 angularjs视频教程 jquery解析json数据 jquery获取元素宽度 查看kafka消费情况 python计算器 python程序 java简介 java发邮件 java的基本类型 java最新框架 java学习文档 java字符串比较 java时间戳转日期 java实现栈 java怎么学 java异常处理 liunx命令大全 linux密码 kafka中文教程 decimalformat 内存整理工具 电脑必备软件排行榜 手机模拟器下载 司司网吧 js跳出for循环 pycharm中文版 网红照片男 foobar2000插件 文件粉碎工具 骰子表情包 苹果手机怎么看内存
当前位置: 首页 > 学习教程  > 编程语言

【LeetCode85】-最大矩形

2021/1/13 19:17:22 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

实现思路: 这题实现的思路是建立 【LeetCode84】-柱状图中最大矩形面积基础之上。 概括来说,解题过程就是遍历每一行,将每一行及该行上面看成直方图,在每一行计算该抽象直方图最大的矩形面积即可。 构造每一行抽象直方图的方法…

实现思路:

这题实现的思路是建立 【LeetCode84】-柱状图中最大矩形面积基础之上。

概括来说,解题过程就是遍历每一行,将每一行及该行上面看成直方图,在每一行计算该抽象直方图最大的矩形面积即可。

构造每一行抽象直方图的方法:判断每一行的位置处是否为0,如果为0那么直方图对应的高度为0,否则高度为该行上一行的高度值加1

实现代码:

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	int getMaxH(vector<int> heights) {
		int amax = 0;
		stack<int>s;
		s.push(-1);
		for (int i = 0;i < heights.size();i++) {
			while (s.top() != -1 && heights[s.top()] >= heights[i]) {
				int cur = s.top();s.pop();
				amax = max(amax, heights[cur] * (i - s.top() - 1));
			}
			s.push(i);
		}
		while (s.top() != -1) {
			int cur = s.top();s.pop();
			int area = heights[cur] * (heights.size() - s.top() - 1);
			amax = max(amax, area);
		}
		return amax;
	}
	int maximalRectangle(vector<vector<char>>& matrix) {
		int rows = matrix.size();
		if (rows == 0) return 0;
		int columns = matrix[0].size();
		if (columns == 0) return 0;
		int amax = 0;
		vector<vector<int>> heights(rows,vector<int>(columns));
		for (int i = 0;i < columns;i++) {
			heights[0][i] = matrix[0][i] == '0' ? 0 : 1;
		}
		for (int i = 1;i < rows;i++) {
			for (int j = 0;j < columns;j++) {
				heights[i][j] = matrix[i][j]=='0'?0: heights[i - 1][j] + 1;
			}
		}
		for (int i = 0;i < rows;i++) {
			amax = max(amax, getMaxH(heights[i]));
		}
		return amax;
	}
};
int main() {
	return 0;
}

提交结果:

在这里插入图片描述

总结:

这道题主要难在怎么和之前直方图求最大矩形结合再一起,以及如何构造抽象的直方图,当理解这两点之后,这道题解起来就十分容易了


本文链接: http://www.dtmao.cc/news_show_600011.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?