最大正方形和最大矩形

· 约 6 分钟阅读 · – 次阅读 leetcode
#dp

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1： 输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出：4

示例 2： 输入：matrix = [[“0”,“1”],[“1”,“0”]] 输出：1

示例 3： 输入：matrix = [[“0”]] 输出：0

暴力法

时间复杂度O(mnmin(m,n)^2), 时间超限

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) {
            return 0;
        }
        int columns = matrix[0].size();
        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    ans = max(ans, 1);
                    int current = min(rows-i, columns-j);
                    for (int k = 1; k < current; k++) {
                        bool flag = true;
                        if (matrix[i+k][j+k] == '0') {
                            flag = false;
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i+k][j+m] == '0' || matrix[i+m][j+k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag){
                            ans = max(ans, k+1);
                        }else{
                            break;
                        }
                    }
                }
            }
        }
        return ans*ans;


    }
};

动态规划

考虑记录dp[i][j]以(i,j)为右下角且只包含1的正方形的边长大小，则：

  1. 当i==0或j==0即边界时，dp[i][j] = 1,
  2. dp[i][j]与左边，上边，左上角三个位置的dp有关
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) {
            return 0;
        }
        int columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns));
        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }else {
                        dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    }
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans*ans;
    }
};

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1: 输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10

示例 2： 输入： heights = [2,4] 输出： 4

暴力法

矩形面积等于 底*高，程序计算的时候，需要固定一个然后遍历另一个。 我们固定高的思路： 对于每一个柱形i，从i向两边遍历，直到严格小于该柱形的边界，则中间部分为底边。

但是无法通过OJ

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        int ans = heights[0];
        for (int i = 0; i < n; i++) {
            // cout << i << " ";
            int left = i-1, right = i+1;
            while (left >= 0 && heights[left] >= heights[i]){
                left--;
            }
            while (right < n && heights[right] >= heights[i]) {
                right++;
            }
            // cout << left << " " << right << " " << heights[i] << endl;
            ans = max(ans, (right-left-1)*heights[i]);
        }
        return ans;

    }
};

单调栈

维持高度值严格单调递增的栈，方便寻找每个柱子的左边界和右边界

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        int ans = heights[0];

        vector<int> left(n), right(n);
        // 单调栈
        stack<int> mono_stack;

        // 找每个柱子左侧第一次低于这个柱子的序号
        for (int i = 0; i < n; i++) {
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]){
                mono_stack.pop();
            }
            left[i] = mono_stack.empty() ? -1 : mono_stack.top();
            mono_stack.emplace(i);
        }

        //找每个柱子右侧第一次低于这个柱子的序号
        mono_stack = stack<int>();
        for (int i = n-1; i >= 0; i--) {
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]){
                mono_stack.pop();
            }
            right[i] = mono_stack.empty() ? n : mono_stack.top();
            mono_stack.emplace(i);
        }

        for (int i = 0; i < n; i++) {
            ans = max(ans, (right[i]-left[i]-1)*heights[i]);
        }

        return ans;

    }
};

做一些常数项的优化，将寻找右边界合并。 注意初始化right默认值为n，因为有可能部分值最后未出栈，右边界为n

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        int ans = heights[0];

        vector<int> left(n), right(n, n);
        // 单调栈
        stack<int> mono_stack;

        // 找每个柱子左侧第一次低于这个柱子的序号
        for (int i = 0; i < n; i++) {
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]){
                // 一个数被弹出时，说明刚好待进栈的数小于栈顶元素。如果存在相同高度，此时边界可能会有差异，但不影响最终值
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }
            left[i] = mono_stack.empty() ? -1 : mono_stack.top();
            mono_stack.emplace(i);
        }

        for (int i = 0; i < n; i++) {
            ans = max(ans, (right[i]-left[i]-1)*heights[i]);
        }

        return ans;

    }
};

85. 最大矩形

给定一个仅包含 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

转化为柱形图

借鉴【柱状图中最大矩形】的思路，将矩形转化为柱状图，然后计算，可得到解。 时间复杂度为O(mnmin(m, n))

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) {
            return 0;
        }
        int columns = matrix[0].size();
        vector<vector<int>> height(rows, vector<int>(columns, 0));
        // 构建柱状图，当然也可以横着构建
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    height[i][j] = i == 0 ?  1 : height[i-1][j] + 1;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                // 一行一行的遍历柱状图，固定h，两边搜索最大矩形的左和右边界。
                int left = j-1, right = j+1;
                int h = height[i][j];
                while (left >= 0 && height[i][left] >= h) {
                    left--;
                }
                while (right < columns && height[i][right] >= h) {
                    right++;
                }
                // cout << i << " " << j << " " << left << " " << right << " " << h << endl;
                ans = max(ans, (right-left-1)*h);
            }
        }
        return ans;
    }
};

柱状图+单调栈

与上一题类似，寻找左右边界的过程可以使用单调栈优化，空间换时间

时间复杂度O(m*n)

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) {
            return 0;
        }
        int columns = matrix[0].size();
        vector<vector<int>> height(rows, vector<int>(columns, 0));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    height[i][j] = i == 0 ?  1 : height[i-1][j] + 1;
                }
            }
        }

        stack<int> mono_stack;
        vector<int> left(columns, 0), right(columns, columns);
        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                while (!mono_stack.empty() && height[i][mono_stack.top()] >= height[i][j]) {
                    right[mono_stack.top()] = j;
                    mono_stack.pop();
                }
                left[j] = mono_stack.empty() ? -1 : mono_stack.top();
                mono_stack.emplace(j);
            }
            for (int j = 0; j < columns; j++) {
                ans = max(ans, (right[j]-left[j]-1)*height[i][j]);
            }
            //注意每一行计算后初始化中间变量
            mono_stack = stack<int>();
            left = vector<int>(columns, 0);
            right = vector<int>(columns, columns);
        }
        return ans;
    }
};