https://leetcode.cn/problems/stamping-the-grid/description/
一、题目解析
1.1 题意
给一个 m×n 的网格 grid，0 是空地，1 是障碍物。你有一枚 stampHeight × stampWidth 的邮票，只能贴在全为 0 的矩形区域上。邮票可以重叠，同一个格子可以被多张邮票覆盖。问：能不能用若干枚邮票盖满所有 0 格子？
1.2 两个核心问题
这道题要同时解决两件事：
查询——能不能贴。 以 (i,j) 为左上角放一枚邮票，邮票覆盖的矩形区域里有没有障碍物？暴力需要遍历区域内每个格子，O(stampHeight × stampWidth)。
修改——标记覆盖。 确定能贴之后，把这片区域标记为"已覆盖"。暴力同样要逐个格子写，O(stampHeight × stampWidth)。
m×n 最大 2×10^5，邮票面积可以接近整个网格，暴力是 O(mnHW)，直接炸。两个操作都必须压到 O(1)——前缀和管查询，差分管修改。
二、二维前缀和：能不能贴
前缀和的作用是 O(1) 回答"任意矩形区域里元素和是多少"。构建公式：
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + grid[i-1][j-1]prefixSum[i][j] 表示从 (0,0) 到 (i-1,j-1) 这个矩形区域的元素总和。数组开 (row+1)×(col+1)，第 0 行和第 0 列天然为 0，边界不用特判。
对于 0-indexed 区域 [r1,c1] 到 [r2,c2] 的查询：
sum = prefixSum[r2+1][c2+1] - prefixSum[r2+1][c1] - prefixSum[r1][c2+1] + prefixSum[r1][c1]四项加减就是二维容斥：拿整个大矩形减去左边一条、减去上边一条，再把左上角被减了两次的那块加回来。
如果 sum == 0，说明区域内没有 1，全是空地，可以贴邮票。这就是代码 Part 1 做的事。
三、二维差分：标记覆盖
确定某个位置能贴，就用二维差分 O(1) 记录"这片区域 +1 层覆盖"。邮票可以重叠，策略是贪心的——每个能贴的位置都贴上，反正多贴不会把已覆盖的格子变没。
邮票左上角 (r1,c1)，右下角 (r2,c2)，四角标记如下：
diff[r1+1][c1+1] += 1 // 覆盖起点，影响向右下扩散diff[r1+1][c2+2] -= 1 // 右边界外一列，截断横向扩散diff[r2+2][c1+1] -= 1 // 下边界外一行，截断纵向扩散diff[r2+2][c2+2] += 1 // 右下被截断两次，补回下标偏移 +1 和 +2 是因为 diff 开到了 row+2，还原公式走的是 1-indexed 前缀和。r2+2 最大等于 (row-1)+2 = row+1。
还原用二维前缀和：对 diff 再做一次前缀和，标记展开为实际覆盖层数：
diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]
四、代码详解
class Solution { public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) { int row = grid.length; int col = grid[0].length; // prefixSum 开 row+1，1-indexed，第 0 行/列是哨兵 int[][] prefixSum = new int[row + 1][col + 1]; // diff 开 row+2，四角标记最大下标到 row+1 int[][] diff = new int[row + 2][col + 2]; // ===== Part 1：构建前缀和 ===== for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { prefixSum[i][j] = prefixSum[i][j - 1] + prefixSum[i - 1][j] + grid[i - 1][j - 1] - prefixSum[i - 1][j - 1]; } } // ===== Part 2：贪心贴邮票 ===== for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int row1 = i; int col1 = j; int row2 = i + stampHeight - 1; int col2 = j + stampWidth - 1; // 邮票右下角超出网格，这个左上角位置没法贴 if (row2 >= row || col2 >= col) { continue; } // 前缀和 O(1) 判断区域内是否有障碍物 int locationSum = prefixSum[row2 + 1][col2 + 1] - prefixSum[row2 + 1][col1] - prefixSum[row1][col2 + 1] + prefixSum[row1][col1]; // 区域内全为 0，可以贴 if (locationSum == 0) { // 二维差分四角标记，O(1) 完成区域覆盖 diff[row1 + 1][col1 + 1] += 1; diff[row1 + 1][col2 + 2] -= 1; diff[row2 + 2][col1 + 1] -= 1; diff[row2 + 2][col2 + 2] += 1; } } } // ===== Part 3：差分还原 + 最终检查 ===== for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { // 二维前缀和还原：标记 + 上 + 左 - 左上 diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]; // 空地且未被任何邮票覆盖 → 失败 if (diff[i][j] == 0 && grid[i - 1][j - 1] == 0) { return false; } } } return true; }}为什么可以贪心。 邮票可以重叠——某张邮票贴上去，只会让覆盖层数 +1，不会把原本已覆盖的格子变成未覆盖。所以不需要做"贴或不贴"的决策，每个能贴的位置都直接贴上就行。
**diff 开 row+2 ： r2 最大 row-1，标记写到 r2+2 ≤ row+1。diff 开到 row+2 正好兜住。col 方向同理。
两个前缀和公式的对应关系。 Part 1 的 prefixSum[i][j] = ... + grid[i-1][j-1] 是从原数组构建前缀和；Part 3 的 diff[i][j] += ... 是从差分标记还原为实际值。都是同一个容斥：当前 = 左 + 上 − 左上 + 自身。
最终检查的逻辑。 diff[i][j] 是格子 (i-1,j-1) 被覆盖的总层数。如果这个格子本是空地（grid0）但层数为 0，说明没有任何邮票覆盖到它，返回 false。
五、复杂度分析
时间 O(row × col)：三次独立遍历网格：Part 1 构建前缀和、Part 2 贪心贴邮票、Part 3 差分还原，每次都是遍历全部格子，代入最大约为 2×10^5。
空间 O(row × col)：prefixSum 和 diff 各占一份。
本文由 AgentPlanFlow 生成