题目

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6.

分析

求给定只包含'0'和‘1’的矩阵中，由连续的‘1’组成的最大矩阵面积。这道题基于直方图的最大长方形的延伸，听过左神在牛客上的算法精讲课的小伙伴应该都有很清晰的思路。 这道题的关键就是 先将矩阵转化为数组，算法原型即求直方图的最大面积。

代码

/* LeetCode 85_Maximal Rectangle.cpp */ #include <iostream> #include <cstdlib> #include <vector> #include <stack> #include <algorithm> using namespace std; class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector<int> heights(n, 0); int maxArea = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { ++heights[j]; }else{ heights[j] = 0; }//else }//for maxArea = max(maxArea, largestRectangleArea(heights)); }//for return maxArea; } /*求直方图中最大矩形面积，利用栈*/ int largestRectangleArea(vector<int> &heights) { if (heights.empty()) return 0; int n = heights.size(); int maxArea = 0; stack<int> st; for (int i = 0; i < n; ++i) { /*当前高度高于栈顶索引*/ while (!st.empty() && heights[i] <= heights[st.top()]) { //计算栈顶索引左右扩展对应的最大长方形面积 int idx = st.top(); st.pop(); int left = st.empty() ? -1 : st.top(); int curArea = (i - left - 1)*heights[idx]; maxArea = max(maxArea, curArea); }//if st.push(i); }//for /*检验栈中剩余元素*/ while (!st.empty()) { int idx = st.top(); st.pop(); int left = st.empty() ? -1 : st.top(); int curArea = (n - left - 1)*heights[idx]; maxArea = max(maxArea, curArea); }//while return maxArea; } }; int main() { vector<vector<char>> v = {{'1','0','1','1','1'}, {'0','1','0','1','0'}, { '1','1','0','1','1' }, { '0','1','1','1','1' } }; cout << Solution().maximalRectangle(v) << endl; system("pause"); return 0; }