LeetCode 221. Maximal Square 一个使用了动态规划却和暴力一个性能的解法

class Solution {
public:
    int row, col, ans = 0;
    int maximalSquare(vector<vector<char>>& matrix) {
        row = matrix.size();
        if (row == 0) return 0;
        col = matrix[0].size();
        if (col == 0) return 0;
        
        vector<int> height(col, 0);
        
        for (int i = 0; i < row; ++i){
            for (int j = 0; j < col; ++j){
                height[j] = (matrix[i][j] == '0') ? 0 : height[j] + 1;
            }
            findAns(height);
        }
        
        return ans * ans;
    }
    
    void findAns(vector<int> &height){
        int t = height[0], ncount = 1;
        for (int i = 0; i < height.size(); ++i){
            t = height[i];
            ncount = 1;
            
            int j = i - 1;
            while (j > 0){
                if (height[j] >= t){
                    ++ncount;
                }else{
                    break;
                }
                j--;
            }
            int k = i + 1;
            while (k < height.size()){
                if (height[k] >= t){
                    ++ncount;
                }else{
                    break;
                }
                k++;
            }
            if (ncount >= t){
                ans = max(ans, t);
            }
        }
    }
};
已邀请:

要回复问题请先登录注册

返回顶部