給定一個僅包含0 和 1 的二維二進制矩陣，找出隻包含 1 的最大矩形，并返回其面積。 示例: 輸入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 輸出: 6

// // Created by tannzh on 2020/8/22. // /* * 最大矩形 給定一個僅包含0 和 1 的二維二進制矩陣，找出隻包含 1 的最大矩形，并返回其面積。 示例: 輸入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 輸出: 6 */ #include <iostream> #include <vector> #include <stack> #include <algorithm> using std::max; using std::min; using std::stack; using std::vector; class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if (matrix.empty()) return 0; int max_area = 0; vector<int> height(matrix[0].size(), 0); for (size_t i=0; i<matrix.size(); i) { for (size_t j=0; j<matrix[0].size(); j) if (matrix[i][j] == '0') height[j] = 0; else height[j]; max_area = max(max_area, largestRectangleArea(height)); } return max_area; } private: int largestRectangleArea(vector<int> &height) { int max_area = 0, i = 0, size = height.size(); for (stack<int> stk; i<size || !stk.empty(); ) if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i ); else { int tp = stk.top(); stk.pop(); max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1)); } return max_area; } }; int main(int argc, char **argv) { std::vector<std::vector<char>> matrix = { {'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'} }; Solution s; std::cout << s.maximalRectangle(matrix) << std::endl; return 0; }

0 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0

對于上述這個矩陣，我們人腦是如何第一時間發現中間那坨 1 的呢？我覺得應該有下面這個過程:

_ 0 1 0 0 | |_ 1 1 1 0 |*|*| 0 1 1 0 |*|*| --------------- 0 0 1 0 0 1 0 0

首先一眼排除掉虛線下面的可能性，而上面的部分，怎麼看怎麼像是 [114. Largest Rectangle in Histogram](../114. Largest Rectangle in Histogram) 的圖。顯然如果将層數累加，則成了 height 這個 vector 了。

0 3 2 0

這就完全成了 114 題的解答了。

所以這道題比較偷懶的方法，是直接使用 114 題裡的 largestRectangleArea 方法。并構建出 height 這個 vector 即可。

大部分童鞋和我一樣，遇到這道題的時候，還沒遇到 114, 那麼靈感應該不會那麼突然，常規的思路應該還是 DP。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!