221. Maximal Square (M)

221. Maximal Square
     Medium

3736

93

Add to List

Share
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:

---

我的解法，只想到brute force，然后看答案：

我自己的写法：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        int col = (row>0) ? matrix[0].size():0;
        if (row == 0 or col == 0) return 0;
        
        vector<int> last_dp(col, 0);
        for (int c=0; c<col; ++c) {
            last_dp[c] = (matrix[0][c] == '1') ? 1:0;
        }
        int ans = *max_element(last_dp.begin(), last_dp.end());
        vector<int> curr_dp(col, 0);
        for (int r=1; r<row; ++r) {
            curr_dp[0] = (matrix[r][0] == '1') ? 1:0;
            for (int c=1; c<col; ++c) {
                if (matrix[r][c] == '1') {
                    curr_dp[c] = min({curr_dp[c-1], last_dp[c], last_dp[c-1]}) + 1;
                }
                else {
                    curr_dp[c] = 0;
                }
            }
            ans = max(ans, *max_element(curr_dp.begin(), curr_dp.end()));
            last_dp = curr_dp;
        }
        
        return ans*ans;
    }
};

Runtime: 32 ms, faster than 97.98% of C++ online submissions for Maximal Square.
Memory Usage: 11.4 MB, less than 78.35% of C++ online submissions for Maximal Square.

踩过的坑：

• edge case里面，col需要判断row>0与否
• 我这种写法必须if (row == 0 or col == 0) return 0;， 否则在max_element就会出runtime错
• 答案的写法里面是只需要一行，用prev记录last_dp的[c-1]这个元素
• 答案的dp vector长度是col+1，所以循环index从1到rows闭区间，int i = 1; i <= rows; i++，然后提取matrix元素的时候if (matrix[i - 1][j - 1] == '1')， 这样写起来更加简洁，也不需要第二条的判断了
• stl::max只能提取两个对比元素，或者initializer list，不能提取vector。对于stl container需要用max_element或者min_element来提取

重新写的版本：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        int col = (row>0) ? matrix[0].size():0;
        
        vector<int> dp(col+1, 0);
        
        int ans = 0, temp = 0, prev = 0;
        for (int r=1; r<=row; ++r) {
            for (int c=1; c<=col; ++c) {
                temp = dp[c];
                if (matrix[r-1][c-1] == '1') {
                    dp[c] = min({dp[c-1], dp[c], prev}) + 1;
                }
                else {
                    dp[c] = 0;
                }
                prev = temp;
            }
            ans = max(ans, *max_element(dp.begin(), dp.end()));
            prev = 0; // 其实不需要
        }
        
        return ans*ans;
    }
};

NOTE: 其实prev = 0; 不需要，因为每次新的一行的时候, dp[c-1] 即 dp[0] 永远是0. 从未被更新过！