Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
一道超难的题目,思想难,同时实现也难。
本题是动态规划法的高级应用,还依据题目特征优化,难度相当高。
经提示,知道是max histogram这个题目的思想的灵活运用,就是每一行运用max histogram算法思想计算。
原来LeetCode把max histogram放在这一题之前是有原因的。没有max histogram这一题的思想基础垫底,是很难理解的。
LeetCode论坛上的讨论,其实也是这一思想的变种运用,不过感觉讲得并不清楚,他所谓的拖线法,其实就是histogram的倒置。
只不过并没有严格按照histogram的算法来进行,而是优化了。
我按histogram算法写的程序用了大概100ms左右,他的算法程序能在40-50ms左右,很快。
所以我也不得不研究一下他的算法到底优化了什么。
他使用了三个表L,R,H表,我也画了三个表,对比看看,填填这个表,就能理解这个算法了:
下面是标准的histogram题目算法的应用程序:
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix)
{
int row = matrix.size();
if (row < 1) return 0;
int col = matrix[0].size();
vector<int> his(col);
int maxArea = 0;
for (int i = row-1; i >= 0; i--)
{
formHistogram(matrix, i, his);
maxArea = max(maxArea, maxHistogram(his));
}
return maxArea;
}
void formHistogram(vector<vector<char> > &m, int row, vector<int> &his)
{
for (size_t j = 0; j < m[0].size(); j++)
{
if (m[row][j]-'0' == 0) his[j] = 0;
else if (row != m.size()-1 && m[row+1][j]-'0' == 1)
{
his[j]--;
}
else
{
for (int i = row; i >= 0; i--)
{
if (m[i][j]-'0' == 1) his[j]++;
else break;
}
}
}
}
int maxHistogram(vector<int> &h)
{
h.push_back(0);
int n = h.size();
int maxArea = 0;
stack<int> stk;
for (int i = 0; i < n; )
{
if (stk.empty() || h[stk.top()] <= h[i]) stk.push(i++);
else
{
int t = stk.top();
stk.pop();
maxArea = max(maxArea, h[t]*(stk.empty()? i:i-stk.top()-1));
}
}
return maxArea;
}
};
优化一点histogram算法的程序:
int maxHistogram(vector<int> &h)
{
h.push_back(0);
int n = h.size();
int maxArea = 0;
stack<int> stk;
for (int i = 0; i < n; )
{
if (stk.empty() || h[stk.top()] <= h[i]) stk.push(i++);
else
{
int t = stk.top();
stk.pop();
maxArea = max(maxArea, h[t]*(stk.empty()? i:i-stk.top()-1));
}
}
return maxArea;
}
//================histogram,拖线法实现
int maximalRectangle2(vector<vector<char> > &matrix)
{
int row = matrix.size();
if (row < 1) return 0;
int col = matrix[0].size();
vector<int> his(col);
int maxArea = 0;
for (int i = row-1; i >= 0; i--)
{
for (int j = 0; j < col; j++)
{
if ( matrix[i][j]-'0' == 1) his[j]++;
else his[j] = 0;
}
maxArea = max(maxArea, maxHistogram(his));
}
return maxArea;
}
最后是leetcode上的优化算法,也是上图示意图的算法实现:
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.empty()) {
return 0;
}
int n = matrix[0].size();
vector<int> H(n);
vector<int> L(n);
vector<int> R(n, n);
int ret = 0;
for (int i = 0; i < matrix.size(); ++i) {
int left = 0, right = n;
// calculate L(i, j) from left to right
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++H[j];
L[j] = max(L[j], left);
}
else {
left = j+1;
H[j] = 0; L[j] = 0; R[j] = n;
}
}
// calculate R(i, j) from right to right
for (int j = n-1; j >= 0; --j) {
if (matrix[i][j] == '1') {
R[j] = min(R[j], right);
ret = max(ret, H[j]*(R[j]-L[j]));
}
else {
right = j;
}
}
}
return ret;
}
2014-2-27 update:
还是下面这个程序比较保险,虽然leetcode上测试,是上一个程序比较快,但是按照理论上计算,两个算法的时间复杂度都是O(n*n),而空间复杂度也都是O(n),那么其实两个方法的实际运行速度都应该差不多的。
而且主要是下面这个程序更加模块化,更简易;上一个程序很容易出错,下标处理起来很麻烦的,一不小心结果就会出错。
int maximalRectangle(vector<vector<char> > &matrix)
{
if (matrix.empty() || matrix[0].empty()) return 0;
vector<int> height(matrix[0].size()+1);
int max_area = 0;
for (int i = 0; i < matrix.size(); i++)
{
for (int j = 0; j < matrix[0].size(); j++)
{
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
max_area = max(max_area, maxHistogram(height));
}
return max_area;
}
int maxHistogram(vector<int> &height)
{
int ans = 0;
stack<int> stk;
for (int i = 0; i < height.size(); )
{
if (stk.empty() || height[stk.top()] < height[i]) stk.push(i++);
else
{
int idx = stk.top();
stk.pop();
ans = max(ans, (stk.empty()? i:i-stk.top()-1)*height[idx]);
}
}
return ans;
}
分享到:
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
1. Introduction 2. Array i. Remove Element ... Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码...Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. ...
Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal ...
100个leetCode详细解答
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 ...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...