LeetCode 30 days Challenge - Day 27

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

题目要求分析：给定一个值为0或1的二维数组，求其中由1组成的、面积最大的正方形面积。

解法：

本题使用动态规划思想，其中dp[i][j]记录以i、j为右下角坐标的正方形的最大边长，从左往右，从上往下遍历一遍数组，并记录其中出现过的最大边长，返回结果即为最大边长的平方。

dp数组按照以下规则进行更新：

对i，j：满足以i、j为右下角坐标的正方形边长范围是1 - (min(i, j) + 1)，这些边长的正方形中只要有一个元素不为1，则不能加入结果。
根据动态规划的思想：当前状态只与其上一个状态有关，即对于上述以i、j为右下角坐标的正方形，边长为 (min(i, j) + 1)的正方形就是当前状态，因此需要考虑其上一个状态即边长为min(i, j)的正方形是如何影响当前状态的。
不难发现，边长为 (min(i, j) + 1)的正方形除去最右下角元素后含有三个边长为min(i, j)的正方形（分别是去除最右列、最下行，去除最右列、最上行，去除最左列、最下行三种情况），当且仅当这三个正方形都全是1、且位置(i, j)也是1时，dp[i][j]取值为(min(i, j) + 1)；
综上，规则为：dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1

下图展示了遍历过程中三种情况：

注：最终求的是面积，注意返回最大边长的平方。

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;
    int res = 0, m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
                res = max(res, dp[i][j]);
            }
        }
    }
    return res * res;
}

传送门：Maximal Square

Karl

Karl's Nest

leetcode-day-27

LeetCode 30 days Challenge - Day 27

Maximal Square

Solution