Hard

题目描述

给你一个 m x n 的二进制矩阵 grid，每个格子要么是 0（空）要么是 1（被占据）。

现在你有邮票，邮票的尺寸为 stampHeight x stampWidth。我们想要贴邮票，使其满足以下限制和要求：

  • 覆盖所有的空格子。
  • 不覆盖任何被占据的格子。
  • 我们可以放任意数量的邮票。
  • 邮票可以相互重叠。
  • 邮票不允许旋转。
  • 邮票必须完全在网格内。

如果可以在满足上述限制和要求的前提下放置邮票，返回 true；否则返回 false。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们有两个重叠的邮票（在图中标记为 1 和 2）能够覆盖所有的空格子。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2
输出：false
解释：没有办法在不让邮票超出网格的情况下将邮票放在所有空格子上。

提示：

  • m == grid.length
  • n == grid[r].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 2 * 10^5
  • grid[r][c] 不是 0 就是 1
  • 1 <= stampHeight, stampWidth <= 10^5

解题思路

这道题的核心思路是：贪心地放置邮票，然后检查是否所有空格都被覆盖。

算法步骤：

  1. 构建前缀和矩阵：用于快速计算任意子矩形区域内被占据格子的数量，判断是否可以放置邮票。

  2. 贪心放置邮票：遍历所有可能的邮票左上角位置，如果该位置可以放置邮票（即邮票覆盖范围内没有被占据的格子），就在该位置放置邮票。

  3. 构建覆盖矩阵：记录每个格子被邮票覆盖的情况。使用二维差分数组来高效标记邮票覆盖的区域。

  4. 检查覆盖完整性：最后检查所有空格子是否都至少被一个邮票覆盖。

关键技巧：

  • 使用前缀和快速判断区域内是否有障碍物（时间复杂度O(1)）
  • 使用二维差分数组高效标记邮票覆盖区域
  • 贪心策略：尽可能多地放置邮票，不会影响最优解

时间复杂度分析：

  • 构建前缀和：O(mn)
  • 贪心放置邮票：O(mn)
  • 构建和检查覆盖：O(mn)
  • 总时间复杂度：O(mn)

这种方法能够高效处理大规模数据，满足题目约束条件。

代码实现

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size(), n = grid[0].size();
        
        // 构建前缀和数组
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j];
            }
        }
        
        // 差分数组，用于标记邮票覆盖
        vector<vector<int>> diff(m + 2, vector<int>(n + 2, 0));
        
        // 贪心放置邮票
        for (int i = 0; i <= m - stampHeight; i++) {
            for (int j = 0; j <= n - stampWidth; j++) {
                int i2 = i + stampHeight - 1, j2 = j + stampWidth - 1;
                // 检查这个区域是否可以放邮票（没有被占据的格子）
                int sum = prefix[i2 + 1][j2 + 1] - prefix[i][j2 + 1] - prefix[i2 + 1][j] + prefix[i][j];
                if (sum == 0) {
                    // 在差分数组中标记这个区域
                    diff[i + 1][j + 1]++;
                    diff[i + 1][j2 + 2]--;
                    diff[i2 + 2][j + 1]--;
                    diff[i2 + 2][j2 + 2]++;
                }
            }
        }
        
        // 从差分数组恢复实际覆盖情况并检查
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diff[i + 1][j + 1] += diff[i][j + 1] + diff[i + 1][j] - diff[i][j];
                if (grid[i][j] == 0 && diff[i + 1][j + 1] == 0) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        m, n = len(grid), len(grid[0])
        
        # 构建前缀和数组
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j]
        
        # 差分数组，用于标记邮票覆盖
        diff = [[0] * (n + 2) for _ in range(m + 2)]
        
        # 贪心放置邮票
        for i in range(m - stampHeight + 1):
            for j in range(n - stampWidth + 1):
                i2, j2 = i + stampHeight - 1, j + stampWidth - 1
                # 检查这个区域是否可以放邮票（没有被占据的格子）
                area_sum = prefix[i2 + 1][j2 + 1] - prefix[i][j2 + 1] - prefix[i2 + 1][j] + prefix[i][j]
                if area_sum == 0:
                    # 在差分数组中标记这个区域
                    diff[i + 1][j + 1] += 1
                    diff[i + 1][j2 + 2] -= 1
                    diff[i2 + 2][j + 1] -= 1
                    diff[i2 + 2][j2 + 2] += 1
        
        # 从差分数组恢复实际覆盖情况并检查
        for i in range(m):
            for j in range(n):
                diff[i + 1][j + 1] += diff[i][j + 1] + diff[i + 1][j] - diff[i][j]
                if grid[i][j] == 0 and diff[i + 1][j + 1] == 0:
                    return False
        
        return True

public class Solution {
    public bool PossibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.Length, n = grid[0].Length;
        
        // 构建前缀和数组
        int[,] prefix = new int[m + 1, n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1, j + 1] = prefix[i, j + 1] + prefix[i + 1, j] - prefix[i, j] + grid[i][j];
            }
        }
        
        // 差分数组，用于标记邮票覆盖
        int[,] diff = new int[m + 2, n + 2];
        
        // 贪心放置邮票
        for (int i = 0; i <= m - stampHeight; i++) {
            for (int j = 0; j <= n - stampWidth; j++) {
                int i2 = i + stampHeight - 1, j2 = j + stampWidth - 1;
                // 检查这个区域是否可以放邮票（没有被占据的格子）
                int sum = prefix[i2 + 1, j2 + 1] - prefix[i, j2 + 1] - prefix[i2 + 1, j] + prefix[i, j];
                if (sum == 0) {
                    // 在差分数组中标记这个区域
                    diff[i + 1, j + 1]++;
                    diff[i + 1, j2 + 2]--;
                    diff[i2 + 2, j + 1]--;
                    diff[i2 + 2, j2 + 2]++;
                }
            }
        }
        
        // 从差分数组恢复实际覆盖情况并检查
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diff[i + 1, j + 1] += diff[i, j + 1] + diff[i + 1, j] - diff[i, j];
                if (grid[i][j] == 0 && diff[i + 1, j + 1] == 0) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var possibleToStamp = function(grid, stampHeight, stampWidth) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Create prefix sum array to quickly check if area has occupied cells
    const prefix = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
    
    // Function to get sum in rectangle from (r1,c1) to (r2,c2) inclusive
    const getSum = (r1, c1, r2, c2) => {
        return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1];
    };
    
    // Check which positions can place stamps
    const canPlace = Array(m).fill(0).map(() => Array(n).fill(false));
    for (let i = 0; i <= m - stampHeight; i++) {
        for (let j = 0; j <= n - stampWidth; j++) {
            if (getSum(i, j, i + stampHeight - 1, j + stampWidth - 1) === 0) {
                canPlace[i][j] = true;
            }
        }
    }
    
    // Create prefix sum for canPlace array
    const stampPrefix = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            stampPrefix[i][j] = (canPlace[i-1][j-1] ? 1 : 0) + stampPrefix[i-1][j] + stampPrefix[i][j-1] - stampPrefix[i-1][j-1];
        }
    }
    
    // Function to get stamp count that can cover position (r,c)
    const getStampCount = (r, c) => {
        const r1 = Math.max(0, r - stampHeight + 1);
        const c1 = Math.max(0, c - stampWidth + 1);
        const r2 = Math.min(m - stampHeight, r);
        const c2 = Math.min(n - stampWidth, c);
        
        if (r1 > r2 || c1 > c2) return 0;
        
        return stampPrefix[r2+1][c2+1] - stampPrefix[r1][c2+1] - stampPrefix[r2+1][c1] + stampPrefix[r1][c1];
    };
    
    // Check if all empty cells can be covered
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0 && getStampCount(i, j) === 0) {
                return false;
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn)需要遍历网格构建前缀和、放置邮票和检查覆盖
空间复杂度O(mn)需要额外的前缀和数组和差分数组

相关题目