博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Leetcode No.85 *
阅读量:5114 次
发布时间:2019-06-13

本文共 1051 字,大约阅读时间需要 3 分钟。

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例:

输入:[  ["1","0","1","0","0"],  ["1","0","1","1","1"],  ["1","1","1","1","1"],  ["1","0","0","1","0"]]输出: 6 解答:对于此类问题,可以用递归来处理。这个问题可以转化成求柱状图的最大面积,具体转化方式如下: 以列为单位构建柱状图高度,若 v[m][n] 对应点的值为0,那么 v[m+1][n]的高度值需要重新统计;否则高度值进行累加。 然后通过对构建的每一行柱状图采用求最大面积的求法得出结果。
int maximalRectangleHelper(vector
height){ int res = 0; height.push_back(0); stack
s; for(int i=0;i<(signed)height.size();i++) { if(s.empty() || height[s.top()] < height[i] ) s.push(i); else { int curr = s.top(); s.pop(); res = max(res, height[curr] * (s.empty()?i: i-s.top()-1)); i--; } } return res;}//85int maximalRectangle(vector
>& matrix){ if(matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector
height(n,0); int res=0; for(int i=0;i

 

转载于:https://www.cnblogs.com/2Bthebest1/p/10834459.html

你可能感兴趣的文章
NOIP2013 提高组 Day1
查看>>
个人对vue生命周期的理解
查看>>
cocos2dx 3.x simpleAudioEngine 长音效被众多短音效打断问题
查看>>
存储(硬件方面的一些基本术语)
查看>>
观察者模式
查看>>
Weka中数据挖掘与机器学习系列之基本概念(三)
查看>>
Win磁盘MBR转换为GUID
查看>>
大家在做.NET B/S项目的时候多用什么设技术啊?
查看>>
Java SE和Java EE应用的性能调优
查看>>
Android设计模式系列--原型模式
查看>>
免费的论文查重网站
查看>>
C语言程序第一次作业
查看>>
leetcode-Sort List
查看>>
中文词频统计
查看>>
了解node.js
查看>>
想做移动开发,先看看别人怎么做
查看>>
Eclipse相关集锦
查看>>
虚拟化架构中小型机构通用虚拟化架构
查看>>
继承条款effecitve c++ 条款41-45
查看>>
HTML+CSS学习笔记(九)
查看>>