怎样做QQ网站呢,青岛福瀛建设集团有限公司网站,建筑行业做网站,举报网站建设情况 汇报题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例 1#xff1a; 输入#xff1a;matrix [[1,0,1,0,0],[1…题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。
示例 1 输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出6
解释最大矩形如上图所示。示例 2
输入matrix []
输出0示例 3
输入matrix [[0]]
输出0示例 4
输入matrix [[1]]
输出1示例 5
输入matrix [[0,0]]
输出0提示
rows matrix.lengthcols matrix[0].length1 row, cols 200matrix[i][j] 为 0 或 1
解答
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {// 利用 84.柱状图中最大的矩形的思路// 在每一行最左边建立一个坐标轴每列连续1的数量就是矩形高度// 就可以转换为求柱状图中最大的矩形if(matrix.size() 0){return 0;}vectorint heights(matrix[0].size());int maxArea;// 每一行都求一次最大矩形for(int row 0; row matrix.size(); row){// 求出某一行每列的高度for(int col 0; col matrix[0].size(); col){if(matrix[row][col] 1){heights[col] 1;}else // 同一列1不连续高度重置为1{heights[col] 0;}}maxArea max(maxArea, largestRectangleArea(heights));}return maxArea;}// 求每行的最大矩形int largestRectangleArea(vectorint heights){int maxArea 0;stackint st;int p 0;while(p heights.size()){// 栈空入栈if(st.empty()){st.push(p);p;}else {int top st.top();// 当前高度大于栈顶入栈// 保证栈顶到栈底降序if(heights[p] heights[top]){st.push(p);p;}else // 当前高度小于小于栈顶对应的右边界出栈{int height heights[st.top()];st.pop();// 左边第一个小于当前柱子的下标int left st.empty() ? -1 : st.top();// 右边第一个小于当前柱子的下标int right p;maxArea max(maxArea, (right - left - 1) * height);}}}// 【左边界】从【右往左】扩展进行判断是否得到最大矩形while(!st.empty()) // 柱状图完全递增的情况{int height heights[st.top()];st.pop();// 左边第一个小于当前柱子下标int left st.empty() ? -1 : st.top();// 右边没有小于当前高度的柱子int right heights.size();maxArea max(maxArea, (right - left - 1) * height);}return maxArea;}
};
