给出一个只包含0和1的二维矩阵,找出最大的全部元素都是1的长方形区域,返回该区域的面积。
/* * 本体解法基于84. Largest Rectangle in Histogram * 把每一行看成求直方图中最大矩形面积问题 */ public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int m = matrix.length, n = matrix[0].length; int max = 0; int[] h = new int[n]; for (int i = 0; i < m; i++) { Stack<Integer> stack = new Stack<Integer>(); stack.push(-1); for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') h[j] += 1; else h[j] = 0; } for (int j = 0; j < n; j++) { while (stack.peek() != -1 && h[j] < h[stack.peek()]) { int top = stack.pop(); max = Math.max(max, (j - 1 - stack.peek()) * h[top]); } stack.push(j); } while (stack.peek() != -1) { int top = stack.pop(); max = Math.max(max, (n - 1 - stack.peek()) * h[top]); } } return max; }
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { int ret = 0; if(matrix.empty()|| matrix[0].empty()){ return ret; } int m = matrix.size(); int n = matrix[0].size(); for(int i = 0; i < m; i++){ vector<int> temp(n, 0); for(int j = 0; j < n; j++){ int r = i; while(r>=0 && matrix[r][j] == '1'){ temp[j]++; r--; } } ret = max(ret, largestRectangleArea(temp)); } return ret; } int largestRectangleArea(vector<int>& heights) { heights.push_back(0); int result = 0; stack<int> s; for(int i = 0; i < heights.size(); ){ if(s.empty() || heights[i] >= heights[s.top()]){ s.push(i); i++; }else{ int temp = s.top(); s.pop(); result = max(result, (s.empty() ? i : i-s.top()-1)*heights[temp]); } } return result; } };
//参考最高票Java版答案,主要思路就是直方图求最大面积 class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.size()==0) return 0; int m = matrix.size(); int n = matrix[0].size(); vector<int> h(n); int maxS = 0; int num; stack<int> st; st.push(-1); for(int i=0;i<m;i++) { //求当前第i行往上连续1的个数,不连续就置为0,方便下一行统计 //j表示列号,即直方图的连续序号 for(int j=0;j<n;j++) { if(matrix[i][j]=='1') h[j]++; else h[j] = 0; } for(int j=0;j<n;j++) { //这里主要思路是遇到上升序列就入栈,遇到下降序列就计算当前前一个直方图(即当前栈顶序号) //到所有依次出栈(即降序且大于j指向直方图的高度)直方图的距离,然后乘以出栈直方图的高度, //即为当前的面积(不一定最大),剩下的序列依然是升序的,迭代下去 while(st.top()!=-1 && h[j]<h[st.top()]) { num = st.top(); st.pop(); maxS = max(maxS,(j-1-st.top())*h[num]); } st.push(j); } //计算栈中最后一个上升序列的面积(方法同上) while(st.top()!=-1) { num = st.top(); st.pop(); maxS = max(maxS,(n-1-st.top())*h[num]); } } return maxS; } };
/* * 目的:最大区域面积 * 方法:参考leetCode的答案,将每一行都看成一个直方图,最后求直方图所能组成的最大面积 */ int maximalRectangle(vector<vector<char> > &matrix) { int maxVal = 0; int row = matrix.size(); if (row==0) return 0; int col = matrix[0].size(); stack<int>store; vector<int>height(col); for (int i = 0; i < row; ++i){ for (int j = 0; j < col;++j){ if (matrix[i][j] == '1'){ height[j]++; } else{ height[j] = 0; } } for (int j = 0; j < col; ++j){ while(!store.empty() && height[j]<height[store.top()]){ int index = store.top(); store.pop(); int k = store.empty()?-1:store.top(); int area = (j-k-1)*height[index]; maxVal = max(area,maxVal); } store.push(j); } while(!store.empty()){ int index = store.top(); store.pop(); int k = store.empty()?-1:store.top(); int area = (col-k-1)*height[index]; maxVal = max(area,maxVal); } } return maxVal; }
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { int rows = matrix.size(); if(rows <= 0 ) return 0; int cols = matrix[0].size(),maxH[cols]; int maxArea = 0; for (int m = 0; m < rows; m ++) { for (int i = 0; i < cols; i++) { if (matrix[m][i] == '1') maxH[i] = 1; else maxH[i] = 0; } for (int j = 0; j < cols; j++) { int w = 1,l = j - 1, r = j + 1; while (l >= 0 && maxH[l] <= maxH[j] && maxH[l] > 0) {l--;w++;} while (r < cols && maxH[r] <= maxH[j] && maxH[r] > 0) {r++;w++;} if (w * maxH[j] > maxArea) maxArea = w * maxH[j]; } for (int i = m+1; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == '1' && maxH[j] > 0 ) {maxH[j]++;} else {maxH[j] = 0;} } for (int j = 0; j < cols; j++) { int w = 1,l = j - 1, r = j + 1; while (l >= 0 && maxH[l] <= maxH[j] && maxH[l] > 0) {l--;w++;} while (r < cols && maxH[r] <= maxH[j] && maxH[r] > 0) {r++;w++;} if (w * maxH[j] > maxArea) maxArea = w * maxH[j]; } } } return maxArea; } };
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { int m = matrix.size(); int n = matrix[0].size(); if(m==0 || n==0) return 0; int Max = (matrix[0][0]==1?1:0); int l = 0, r = n; vector<int> h(n,0), left(n,0), right(n,n); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) h[j] = (matrix[i][j]=='1' ? h[j]+1:0); l = 0; for(int j=0;j<n;j++) { if(matrix[i][j] == '1') left[j] = max(left[j], l); else{ left[j] = 0; l = j + 1; } } r = n; for(int j=n-1;j>=0;j--) { if(matrix[i][j] == '1') right[j] = min(right[j], r); else{ right[j] = n; r = j; } } for(int j=0;j<n;j++) Max = max(Max, h[j]*(right[j]-left[j])); } return Max; } };
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.size()==0) return 0; int cols = matrix[0].size(); int* hist = new int[cols](); // 以某一行为起头对应该列的最大矩形(列连续1个数) int max_ = 0; for(int i=0; i<matrix.size(); i++) { for(int j=0; j<cols; j++) { if(matrix[i][j]=='1') hist[j] += 1; else hist[j] = 0; } max_ = max(max_, maxRectInHistogram(hist, cols) ); } delete [] hist; hist = nullptr; return max_; } int maxRectInHistogram(int hist[], int n) { int* arr = new int[n];// 申请一个额外的数组 以i为结尾的最大面积 arr[0] = hist[0]; int m = hist[0]; // 最大面积 for(int i=1; i<n; i++) { arr[i] = hist[i]; int temp = hist[i]; for(int j=i-1; j>=0 && hist[j] > 0; j--) { temp = min(temp,hist[j]); arr[i] = max(arr[i],temp*(i-j+1)); } if(m < arr[i]) m = arr[i]; } delete [] arr; arr = nullptr; return m; } };
// 从有“1”的地方开始搜索 public class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0) return 0; int max = 0; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[0].length; j++){ if(matrix[i][j] == '0') continue; int width = Integer.MAX_VALUE; for(int p = i; p < matrix.length; p++){ if(matrix[p][j] == '0') break; for(int q = j; q < matrix[0].length; q++){ if(matrix[p][q] == '0' || q == matrix[0].length - 1){ int curwid; if(matrix[p][q] == '1') curwid = q - j + 1; else curwid = q - j; if(curwid < width) width = curwid; int curS = width * (p - i + 1); if(curS > max) max = curS; break; } } } } } return max; } }
}
//最渣的版本 class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.size()==0) return 0; int rows=matrix.size(); int cols=matrix[0].size(); int MAX=0; vector<int >temp(cols,0); vector<vector<int > >result; for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { temp[j]=matrix[i][j]-'0'+(matrix[i][j]-'0')*temp[j]; } MAX=max(largestRectangleArea(temp),MAX); } return MAX; } int largestRectangleArea(vector<int> &height) { int MAXAREA=0; for(int i=0;i<height.size();i++) { int MIN=height[i]; for(int j=i;j<height.size();j++) { MIN=min(MIN,height[j]); int CurArea=MIN*(j-i+1); if(CurArea>MAXAREA) { MAXAREA=CurArea; } } } return MAXAREA; } };
从这个问题想到单调栈结构
确实有点不容易,我们举例说明:
0 0 1 1 0 1 1
0 0 1 1 1 0 1
0 1 1 1 1 1 0
1 0 0 0 0 1 1
然后将每个元素转化为该元素及上面相连的1的个数和:
0 0 1 1 0 1 1
0 0 2 2 1 0 2
0 1 3 3 2 1 0
1 0 0 0 0 2 1
以第3行为例,转化成柱形图,下图:
是不是很熟悉呢?对的,其实这就是单调栈结构的一个典型应用,以求上面图片中最大矩形面积为例,单调栈的实现如下(建议作为单调栈题目的模版去记忆):
int monotoneStack(vector<int> &vec) { stack<int> st; vec.push_back(0); // ➤ 添加一个0可以在循环的最后一步清空栈 int maxVal = 0; for (int i = 0; i < vec.size(); ++i) { // 这里用单调递增栈 while (!st.empty() && vec[i] < vec[st.top()]) { int height = vec[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - (left+1); maxVal = max(maxVal, height * width); } st.push(i); } return maxVal; }
完整代码如下:
// // Created by jt on 2020/9/2. // #include <vector> #include <stack> using namespace std; class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if (matrix.empty() || matrix[0].empty()) return 0; vector<vector<int> > tmp(matrix.size(), vector<int>(matrix[0].size())); // 第一次遍历:将char型数组转化为int型数组 for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { tmp[i][j] = matrix[i][j] - '0'; } } // 第二次遍历:转化矩阵 for (int i = 1; i < tmp.size(); ++i) { for (int j = 0; j < tmp[0].size(); ++j) { if (tmp[i][j] == 1) tmp[i][j] = tmp[i - 1][j] + 1; } } // 第三次遍历:单调递增栈求最大矩阵面积 int maxVal = 0; for (int i = 0; i < tmp.size(); ++i) { maxVal = max(maxVal, monotoneStack(tmp[i])); } return maxVal; } private: int monotoneStack(vector<int> &vec) { stack<int> st; vec.push_back(0); // ➤ 添加一个0可以在循环的最后一步清空栈 int maxVal = 0; for (int i = 0; i < vec.size(); ++i) { // 这里用单调递增栈 while (!st.empty() && vec[i] < vec[st.top()]) { int height = vec[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - (left+1); maxVal = max(maxVal, height * width); } st.push(i); } return maxVal; } };
class Solution { public: int RectSquare(vector<int> &vec){ int res = 0; vector<vector<int> > dp(vec.size(), vector<int>(vec.size(), 0)); for(int i = 0; i < vec.size(); ++i){ dp[i][i] = vec[i]; } //dp[i][j] 表示i到j的最大面积,dp[i][j + 1] = max(dp[i][j], min(i到j的元素)*(j-i+1)) for(int i = 0; i < vec.size(); ++i){ int cur = vec[i]; res = max(res, cur); for(int j = i + 1; j < vec.size(); ++j){ cur = min(cur, vec[j]); dp[i][j] = max(dp[i][j-1], cur * (j - i + 1)); res = max(res, dp[i][j]); } } return res; } int maximalRectangle(vector<vector<char> > &matrix) { int res = 0; if(matrix.empty()) return res; int m = matrix.size(), n = matrix[0].size(); vector<int> tmp(n, 0); for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ if(matrix[i][j] == '1'){ tmp[j] = tmp[j] + 1; } else tmp[j] = 0; } res = max(res, RectSquare(tmp)); } return res; } };
//利用Largest Rectangle in Histogram的思想,可参考 //https://www.bilibili.com/video/BV1eb411M7Gm?from=search&seid=5986427457100938076 //若matrix有m行,则可以把问题分解成m个Largest Rectangle in Histogram问题 //从上到下遍历matrix的每一行,第i行往上的部分可以看做是Largest Rectangle in Histogram问题中的一个柱形图 class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { int m=matrix.size(); if(m==0) return 0; int n=matrix[0].size(); stack<int>st; st.push(-1); int max_area=0; vector<int>heights(n,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; } for(int j=0;j<n;++j) { while(st.top()!=-1&&heights[j]<heights[st.top()]) { int index=st.top(); st.pop(); max_area=max(max_area,heights[index]*(j-1-st.top())); } st.push(j); } while(st.top()!=-1) { int index=st.top(); st.pop(); max_area=max(max_area,heights[index]*(n-1-st.top())); } } return max_area; } };
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { int n = matrix.size(); int m = matrix[0].size(); if(n == 0 || m == 0) return 0; int max_rec = 0; vector<int> h(m,0); for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ if(matrix[i][j] == '1') h[j]++; else h[j] = 0; } stack<int> sta; sta.push(-1); for(int j = 0; j < m; ++j){ while(sta.top()!= -1 && h[sta.top()] > h[j]){ int tmp = sta.top(); sta.pop(); max_rec = max(max_rec, (j - sta.top()-1)*h[tmp]); } sta.push(j); } while(sta.top()!=-1){ int tmp = sta.top(); sta.pop(); max_rec = max(max_rec, (m - sta.top()-1)*h[tmp]); } } return max_rec; } };
import java.util.Stack; public class Solution { public int maximalRectangle(char[][] matrix) { if(matrix==null||matrix.length==0)return 0; int row = matrix.length,col = matrix[0].length; int max = 0; int[] heights = new int[col]; for(int i = 0;i < row;i++){ for(int j=0;j<col;j++){ if(matrix[i][j]=='1') heights[j]++; else heights[j] = 0; } max = Math.max(max,getMaxRectangle(heights)); } return max; } public int getMaxRectangle(int[] heights){ int n = heights.length; int max = 0,j,k,curMax; Stack<Integer> stk = new Stack<>(); for(int i=0;i<n;i++){ while(!stk.isEmpty()&&heights[stk.peek()]>=heights[i]){ j = stk.pop(); k = stk.isEmpty()?-1:stk.peek(); curMax = (i-k-1)*heights[j]; // curMax = (i-j)*heights[j]; 错误的更新 max = Math.max(curMax, max); } stk.push(i); } while(!stk.isEmpty()){ j = stk.pop(); k = stk.isEmpty()?-1:stk.peek(); curMax = (n-k-1)*heights[j]; //curMax = (n-j)*heights[j]; 错误的更新 max = Math.max(curMax, max); } return max; } }