首页 > 代码库 > LeetCode "Maximal Rectangle"
LeetCode "Maximal Rectangle"
My intuition is flood-fill the BFS solution, which is O(n^4); and then I figured out a DP solution which is O(n^4)..
So I googled some hints: it can be built upon another LeetCode problem: Largest Rectangle in Histogram. With proper pre-calculation, we can make a O(n^3) solution.
Check out my code which completely builds upon my code to "Largest Rectangle in Histogram":
class Solution {public: // struct Rec { Rec() : minH(0), area(0) {}; Rec(int h, int a) : minH(h), area(a) {}; int minH; int area; }; int largestRectangleArea(vector<int> &height) { size_t cnt = height.size(); int max = std::numeric_limits<int>::min(); vector<Rec> dp; dp.resize(cnt); for (int i = 0; i < cnt; i++) { dp[i].minH = height[i]; dp[i].area = height[i]; max = std::max(max, dp[i].area); } // Bottom-Up DP for (int ilen = 2; ilen <= cnt; ilen++) for (int i = 0; i <= cnt - ilen; i++) { int newH = height[i + ilen - 1]; int opH = std::min(dp[i].minH, newH); int newA = opH * ilen; dp[i].minH = opH; dp[i].area = newA; max = std::max(max, newA); } return max; } ////////////// int maximalRectangle(vector<vector<char> > &matrix) { int h = matrix.size(); if (h == 0) return 0; int w = matrix[0].size(); if (w == 0) return 0; vector<vector<int>> pre; pre.resize(h); for (int i = 0; i < h; i++) { pre[i].resize(w); std::fill(pre[i].begin(), pre[i].end(), 0); } // Pre-mark for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { if (matrix[i][j] == ‘1‘) { if (j == 0) pre[i][j] = 1; else pre[i][j] = pre[i][j - 1] + 1; } } // int max = 0; for (int i = 0; i < h; i ++) for (int j = 0; j < w; j ++) { if (matrix[i][j] == ‘1‘) { vector<int> heights; for (int k = i; k < h; k++) { if (pre[k][j] == 0) break; heights.push_back(pre[k][j]); } int currmax = largestRectangleArea(heights); max = std::max(max, currmax); } } return max; }};
LeetCode "Maximal Rectangle"
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。