【leetcode刷题】T163-最大正方形

示例:
输入: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0;
        dp = [0] * len(matrix[0])
        max_size = 0

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '1':
                    dp[j] += 1
                else:
                    dp[j] = 0

            # 统计dp数组中连续>max_size的元素个数
            count = 0
            for j in range(len(matrix[0])):
                if dp[j] > max_size:
                    count += 1
                    if count > max_size:
                        max_size = count;
                        break;
                else:
                    count = 0
        return max_size * max_size

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int max_size = 0;
        vector<int> dp(matrix[0].size(), 0);
        for(int i=0; i < matrix.size(); i++){
            int count = 0;
            for(int j=0; j < matrix[0].size(); j++){
                if(matrix[i][j] == '1')
                    dp[j]++;
                else
                    dp[j] = 0;
            }
            for(int j=0; j < matrix[0].size(); j++){
                // 是否height > max_size的个数 > max_size
                if(dp[j] > max_size){
                    count++;
                    if(count > max_size){
                        max_size = count;
                        break;
                    }
                }else
                    count = 0;
            }
        }
        return max_size * max_size;
    }
};