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题目算法的应用程序：

  1. class Solution {
  2. public:
  3. int maximalRectangle(vector<vector<char> > &matrix)
  4. {
  5. int row = matrix.size();
  6. if (row < 1) return 0;
  7. int col = matrix[0].size();
  8. vector<int> his(col);
  9. int maxArea = 0;
  10. for (int i = row-1; i >= 0; i--)
  11. {
  12. formHistogram(matrix, i, his);
  13. maxArea = max(maxArea, maxHistogram(his));
  14. }
  15. return maxArea;
  16. }
  17. void formHistogram(vector<vector<char> > &m, int row, vector<int> &his)
  18. {
  19. for (size_t j = 0; j < m[0].size(); j++)
  20. {
  21. if (m[row][j]-'0' == 0) his[j] = 0;
  22. else if (row != m.size()-1 && m[row+1][j]-'0' == 1)
  23. {
  24. his[j]--;
  25. }
  26. else
  27. {
  28. for (int i = row; i >= 0; i--)
  29. {
  30. if (m[i][j]-'0' == 1) his[j]++;
  31. else break;
  32. }
  33. }
  34. }
  35. }
  36. int maxHistogram(vector<int> &h)
  37. {
  38. h.push_back(0);
  39. int n = h.size();
  40. int maxArea = 0;
  41. stack<int> stk;
  42. for (int i = 0; i < n; )
  43. {
  44. if (stk.empty() || h[stk.top()] <= h[i]) stk.push(i++);
  45. else
  46. {
  47. int t = stk.top();
  48. stk.pop();
  49. maxArea = max(maxArea, h[t]*(stk.empty()? i:i-stk.top()-1));
  50. }
  51. }
  52. return maxArea;
  53. }
  54. };

优化一点histogram算法的程序：

  1. int maxHistogram(vector<int> &h)
  2. {
  3. h.push_back(0);
  4. int n = h.size();
  5. int maxArea = 0;
  6. stack<int> stk;
  7. for (int i = 0; i < n; )
  8. {
  9. if (stk.empty() || h[stk.top()] <= h[i]) stk.push(i++);
  10. else
  11. {
  12. int t = stk.top();
  13. stk.pop();
  14. maxArea = max(maxArea, h[t]*(stk.empty()? i:i-stk.top()-1));
  15. }
  16. }
  17. return maxArea;
  18. }
  19. //================histogram，拖线法实现
  20. int maximalRectangle2(vector<vector<char> > &matrix)
  21. {
  22. int row = matrix.size();
  23. if (row < 1) return 0;
  24. int col = matrix[0].size();
  25. vector<int> his(col);
  26. int maxArea = 0;
  27. for (int i = row-1; i >= 0; i--)
  28. {
  29. for (int j = 0; j < col; j++)
  30. {
  31. if ( matrix[i][j]-'0' == 1) his[j]++;
  32. else his[j] = 0;
  33. }
  34. maxArea = max(maxArea, maxHistogram(his));
  35. }
  36. return maxArea;
  37. }

最后是leetcode上的优化算法，也是上图示意图的算法实现：

  1. int maximalRectangle(vector<vector<char> > &matrix) {
  2. if (matrix.empty()) {
  3. return 0;
  4. }
  5. int n = matrix[0].size();
  6. vector<int> H(n);
  7. vector<int> L(n);
  8. vector<int> R(n, n);
  9. int ret = 0;
  10. for (int i = 0; i < matrix.size(); ++i) {
  11. int left = 0, right = n;
  12. // calculate L(i, j) from left to right
  13. for (int j = 0; j < n; ++j) {
  14. if (matrix[i][j] == '1') {
  15. ++H[j];
  16. L[j] = max(L[j], left);
  17. }
  18. else {
  19. left = j+1;
  20. H[j] = 0; L[j] = 0; R[j] = n;
  21. }
  22. }
  23. // calculate R(i, j) from right to right
  24. for (int j = n-1; j >= 0; --j) {
  25. if (matrix[i][j] == '1') {
  26. R[j] = min(R[j], right);
  27. ret = max(ret, H[j]*(R[j]-L[j]));
  28. }
  29. else {
  30. right = j;
  31. }
  32. }
  33. }
  34. return ret;
  35. }

2014-2-27 update：

还是下面这个程序比较保险，虽然leetcode上测试，是上一个程序比较快，但是按照理论上计算，两个算法的时间复杂度都是O(n*n)，而空间复杂度也都是O(n)，那么其实两个方法的实际运行速度都应该差不多的。

而且主要是下面这个程序更加模块化，更简易；上一个程序很容易出错，下标处理起来很麻烦的，一不小心结果就会出错。

    1. int maximalRectangle(vector<vector<char> > &matrix)
    2. {
    3. if (matrix.empty() || matrix[0].empty()) return 0;
    4. vector<int> height(matrix[0].size()+1);
    5. int max_area = 0;
    6. for (int i = 0; i < matrix.size(); i++)
    7. {
    8. for (int j = 0; j < matrix[0].size(); j++)
    9. {
    10. if (matrix[i][j] == '1') height[j]++;
    11. else height[j] = 0;
    12. }
    13. max_area = max(max_area, maxHistogram(height));
    14. }
    15. return max_area;
    16. }
    17. int maxHistogram(vector<int> &height)
    18. {
    19. int ans = 0;
    20. stack<int> stk;
    21. for (int i = 0; i < height.size(); )
    22. {
    23. if (stk.empty() || height[stk.top()] < height[i]) stk.push(i++);
    24. else
    25. {
    26. int idx = stk.top();
    27. stk.pop();
    28. ans = max(ans, (stk.empty()? i:i-stk.top()-1)*height[idx]);
    29. }
    30. }
    31. return ans;
    32. }

最新文章

  1. ORA-02020 : 过多的数据库链接在使用中－Windows环境解决步骤
  2. 准备CLR源码阅读环境
  3. 今天工作中遇到的问题！echart.js
  4. 性能测试之Windows常见性能计数器
  5. Epic - Coin Change
  6. oracle：自定义多行合并聚合函数
  7. 获取html上元素的真正坐标
  8. c++ 06
  9. SIFT解析（三）生成特征描述子
  10. Effective C++ ——继承与面向对象设计
  11. Java项目下的classpath路径包括哪里
  12. python之旅4[第四篇]
  13. 6.0-uC/OS-III软件定时器管理
  14. java学习笔记（二）：枚举值
  15. aliyun服务器对象存储oss
  16. php保留两位小数的3种方法
  17. 2018.10.31 NOIP模拟 几串字符（数位dp+组合数学）
  18. sql 基础练习 计算7天各个时间点的总和 group by order mysql一次查询多个表
  19. Stream grouping-storm的流分组策略
  20. python安装lib库

热门文章

  1. sql调优的总结
  2. js阻止冒泡和默认事件
  3. 路由的配置,侧边栏类名与url的结合运用
  4. Error-SQLServer：【失败】win7装SQL server2017
  5. Scrapy下载中间件的优先级（神踏马值越小优先级越高）
  6. NGINX模块开发 之 验证URL參数
  7. Nginx与PHP工作原理
  8. 2019-8-31-dotnet-控制台读写-Sqlite-提示-no-such-table-找不到文件
  9. php+js实现百度地图多点标注的方法
  10. Ubuntu 16.04 配置 L2tp 客户端