85. 最大矩形

题目链接

解题思路

• 暴力怎么做？我们可以枚举，

  • 矩阵的底，必须是第0行，求一个最大值，矩阵的底，必须是第1行，求一个最大值，把所有的都得到，然后最大的那个，就是结果。
  • 依次类推，所有结果的最大值，就是全局最优解

• 举个例子，假设矩阵

  [
  	[1, 0, 1, 0, 0],
  	[1, 0, 1, 1, 1],
  	[1, 1, 1, 1, 1],
  	[1, 0, 0, 1, 0]
  ]
  

  • 怎么求矩阵必须是以第3行为底的最大值？这里用到「二维矩阵」压缩成「一维数组」的技巧，矩阵必须是以第3行为底，原来的矩阵，变成[4, 0, 0, 3, 0]，这咋来的？从第三行往前面看，每一列，最多有多少个连续的1。
  • 然后一维数组上，求84. 柱状图中最大的矩形
  • 为啥这样就是正确的？因为二维矩阵变一维数组的过程，其实就是规定了结果的「高」，然后一维数组上求「柱状图中最大的矩形」，就是规定了结果的「宽」。

代码

class Solution {
public:

    // 一维数组，求「柱状图中最大的矩形」
    int process(vector<int> &nums) {
        stack<int> st;   // 存下标    栈底到栈顶是  小到大
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            while(!st.empty() && nums[i] < nums[st.top()]) {
                int wid_right = i;
                int wid_left = 0;
                int height = nums[st.top()];
                st.pop();
                if (!st.empty()) {
                    wid_left = st.top() + 1;
                }
                ans = max(ans, (wid_right - wid_left) * height);
            }
            st.push(i);
        }
        while(!st.empty()) {
            int wid_right = n;
            int wid_left = 0;
            int height = nums[st.top()];
            st.pop();
            if (!st.empty()) {
                wid_left = st.top() + 1;
            }
            ans = max(ans, (wid_right - wid_left) * height);
        }
        return ans;
    }
    
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> tmp(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    tmp[i][j] = 1;
                    if (i > 0) {
                        tmp[i][j] += tmp[i - 1][j];
                    }
                }
                
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            int res = process(tmp[i]);
            ans = max(ans, res);
        }
        return ans;
    }
};