力扣_数组27—最大矩形

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

思路

• 分别计算以第 $i$ 行为底的最大矩形
• 计算以第 $i$ 行为底的最大矩形
  • 借用“柱状图中最大的矩形”的计算思路
  • 遍历第 $i$ 行，若 $matrix[i][j]==0$，则 $j$ 处柱子高度为 $0$；若 $matrix[i][j]==1$，则 $j$ 处柱子高度为 $matrix[i-1][j]$ 处柱子高度 $+1$
  • 例如：$matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]$
    • 第一层柱状图的高度[“1”,“0”,“1”,“0”,“0”]
    • 第二层柱状图的高度[“2”,“0”,“2”,“1”,“1”]
    • 第三层柱状图的高度[“3”,“1”,“3”,“2”,“2”]
    • 第四层柱状图的高度[“4”,“0”,“0”,“3”,“0”]

代码

class Solution {
   
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
   
        int m = matrix.size();
        int n = matrix[0].size();
        int ret = 0;
        vector<int> row(n, 0);
        for(int i = 0; i < m; i++){
   
            for(int j = 0; j < n; j++){
   
                if(matrix[i][j] == '0')
                    row[j] = 0;
                else
                    row[j] += 1;
            }
            ret = max(ret, largestRectangleArea(row));
        }
        return ret;
    }
    int largestRectangleArea(vector<int>& heights){
   
        int n = heights.size();
        stack<int> stk;
        stk.push(-1);
        vector<int> l2r;
        int ret = 0;
        for(int i = 0; i < n; i++){
   
            while(stk.top() != -1 && heights[stk.top()] >= heights[i]){
   
                ret = max(ret, heights[stk.top()]*(i-l2r[stk.top()]-1));
                stk.pop();
            }
            l2r.push_back(stk.top());
            stk.push(i);
        }
        while(stk.top() != -1){
   
            ret = max(ret, heights[stk.top()]*(n-l2r[stk.top()]-1));
            stk.pop();
        }
        return ret;
    }
};