首页 > 代码库 > 【leetcode】Maximal Rectangle (hard)★
【leetcode】Maximal Rectangle (hard)★
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.
找到01矩形中最大的全1子矩阵。
我自己的思路：
我先用一个跟输入相同大小的矩阵numInCol 存储从当前位置开始向下有多少连续的1。
如
1 0 10 1 11 1 1
其numInCol 是
1 0 30 2 21 1 1
然后用一个变量tmpans来记录以某个位置开始，其右下矩形的最大全1矩阵的大小。
方法是如果当前位置是1，则用1 * numInCol[当前位置] 即只有这一列的大小
如果其后面紧接着的位置也是1，则用 2 * (这两列中连续1高度小的值) 即这两列的矩形大小
如果其后面紧接着的位置也是1，则用 3 * (这三列中连续1高度小的值) 即这三列的矩形大小
........................
依次类推
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;class Solution {public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.empty()) return 0; int row = matrix.size(); int col = matrix[0].size(); int ans = 0; vector<vector<int> > numInCol(row, vector<int>(col, 0)); int tmpans = 0; //对每一列 for(int j = 0; j < col; j++) { numInCol[row - 1][j] = (matrix[row - 1][j] == ‘1‘) ? 1 : 0; for(int i = row - 2; i >= 0; i--) { if(matrix[i][j] == ‘1‘) { numInCol[i][j] = numInCol[i + 1][j] + 1; } } } //对整个矩阵 for(int i = row - 1; i >= 0; i--) { tmpans = numInCol[i][col - 1]; ans = max(ans, tmpans); for(int j = col - 2; j >= 0; j--) { int jj = j; int len = 1; int minlen = numInCol[i][j]; while(jj < col && matrix[i][jj] == ‘1‘) { minlen = min(minlen, numInCol[i][jj]); tmpans = max(tmpans, len * minlen); ans = max(ans, tmpans); jj++; len++; } } } return ans; }};int main(){ Solution s; vector<vector<char> > matrix(4, vector<char>(5, ‘0‘)); matrix[0][1] = ‘1‘; matrix[0][2] = ‘1‘; matrix[0][3] = ‘1‘; matrix[1][1] = ‘1‘; matrix[1][2] = ‘1‘; matrix[2][1] = ‘1‘; matrix[2][2] = ‘1‘; matrix[2][3] = ‘1‘; int ans = s.maximalRectangle(matrix); return 0;}
网上的答案，整体的思路差不多，也是通过一列列的数据来判断，但是并没有像我一样，把所有的值都存下来，而是只存了一行的列信息，每到新的一行再更新，这样空间少了很多。其次，没有像我这样每次都循环后面的列是否为1，而是利用栈，如果高度是递增的就先不计算最大矩形而是把信息压栈，等到遇到高度减少的时候再依次计算这一段的最大矩形。
class Solution {public: int maximalRectangle(vector<vector<char>> &matrix) { if (matrix.empty()) return 0; int rows = matrix.size(); int cols = matrix[0].size(); int maxArea = 0; vector<int> heights(cols + 1, 0); vector<int> stack; for (int i = 0; i < rows; i++) { stack.clear(); for (int j = 0; j < cols + 1; j++) { if (j < cols) { if (matrix[i][j] == ‘1‘) { heights[j]++; } else { heights[j] = 0; } } if (stack.empty() || heights[j] >= heights[stack.back()]) { stack.push_back(j); continue; } while (!stack.empty() && heights[j] < heights[stack.back()]) { int top = stack.back(); stack.pop_back(); int begin = stack.empty() ? 0 : stack.back() + 1; int area = heights[top] * (j - begin); if (area > maxArea) maxArea = area; } stack.push_back(j); } } return maxArea; }};
【leetcode】Maximal Rectangle (hard)★
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。