本文主要是介绍leetcode 85:最大矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
该题与leetcode 84类似，首先对每一行的看做宽度为1的矩阵，如第一行可以表示我1 0 1 0 0的数组 第二行可以表示为2 0 2 1 1的数组，第三行表示为3 1 3 2 2的数组，。。。对每一行数组求最大的柱状图中的最大矩形
方法1：比较笨的方式 时间复杂度较高
int maximalRectangle(std::vector<std::vector<char>>& matrix) {if(matrix.empty())return 0;int width=matrix[0].size();int height=matrix.size();int max=0;for(int i=0;i<height;i++){for(int j=0;j<width;j++){int max1=0;int w1=0;for(int k=j;k<width;k++){if(matrix[i][k]=='1')w1++;elsebreak;}max1=w1;if(w1==0)continue;int flag=0;for(int l=i+1;l<height;l++){int k=j;for(;k<j+w1;k++){if(matrix[l][k]=='0'){w1=(k-j);if((l-i+1)*w1>max1){max1=(l-i+1)*w1;}break;}}if(k==j+w1){if((l-i+1)*w1>max1) {max1=(l-i+1)*w1;}}}if(max<max1)max=max1;}}return max;
}第二种方式：使用找到某个峰值，之后遍历前面数组的方式
int MaxArea(std::vector<int>& heights) {if(heights.size()==0)return 0;int maxArea=0;for(int i=0;i<heights.size();i++){if(i+1<heights.size()&&heights[i]<=heights[i+1])continue;int minH=heights[i];int area=0;for(int j=i;j>=0;j--){minH=std::min(minH,heights[j]);area=minH*(i-j+1);maxArea=std::max(maxArea,area);}}return maxArea;
}
int maximalRectangle(vector<vector<char>>& matrix) {int res = 0;vector<int> height; for (int i = 0; i < matrix.size(); ++i) {height.resize(matrix[i].size());for (int j = 0; j < matrix[i].size(); ++j) {height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);}res = max(res, MaxArea(height));}return res;
}方法三：使用栈的方式
int MaxArea(vector<int> &row){int maxArea=0;row.push_back(0);stack<int> st;for(int i=0;i<row.size();i++){while(!st.empty()&&row[st.top()]>=row[i]) {int cur = st.top();st.pop();maxArea = max(maxArea, (row[cur]) * (st.empty() ? i : i - st.top() - 1));}st.push(i);}return maxArea;
}int maximalRectangle(vector<vector<char>>& matrix) {int res = 0;vector<int> height; for (int i = 0; i < matrix.size(); ++i) {height.resize(matrix[i].size());for (int j = 0; j < matrix[i].size(); ++j) {height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);}res = max(res, MaxArea(height));}return res;
}
这篇关于leetcode 85:最大矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
