221. Maximal Square

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

🧠 Thuật Toán & Kỹ Thuật

Dynamic Programming (Quy hoạch động)Bit Manipulation (Thao tác bit)Matrix (Ma trận)
⏱️ Thời gian O(n×m)
💾 Không gian O(n×m)

💻 Lời Giải

C++ 0221-maximal-square.cpp 
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int edge = 0;
        
        vector<vector<int>> dp(n, vector<int>(m));
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dp[i][j] = matrix[i][j] - '0';
                edge = max(edge, dp[i][j]);
            }
        }
        
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (dp[i][j]) {
                    dp[i][j] += min({
                        dp[i - 1][j], 
                        dp[i][j - 1],
                        dp[i - 1][j - 1]
                    });
                }
                edge = max(edge, dp[i][j]);
            }
        }
        
        return edge*edge;
    }
};