2132. Stamping the Grid[贪心 trick] - 《LeetCode 刷题笔记》

题目解答
题目分析

https://leetcode.com/problems/stamping-the-grid/
好题，一道题学到两个知识！

用来批量更新数组/矩阵区域的方法
贪心思路的设计

题目解答

class Solution:
    def possibleToStamp(self, g: List[List[int]], h: int, w: int) -> bool:
        m, n = len(g), len(g[0])
        height = [[0 for j in range(n)] for i in range(m)]
        height[0] = [1 - x for x in g[0]]
        for i in range(1, m):
            for j in range(n):
                if g[i][j] == 0:
                    height[i][j] = 1 + height[i - 1][j]
                else:
                    height[i][j] = 0
        for i in range(m):
            validHeightCount = 0
            for j in range(n):
                if height[i][j] < h:
                    validHeightCount = 0
                    continue
                validHeightCount += 1
                if validHeightCount < w:
                    continue
                # loop reverse, early break, column by column first
                for jj in range(j, j - w, -1):
                    if g[i][jj] == 1:
                        break
                    for ii in range(i, i - h, -1):
                        if g[ii][jj] == 1:
                            break
                        g[ii][jj] = 1
        for i in range(m):
            for j in range(n):
                if g[i][j] == 0:
                    return False
        return True

题目分析

这道题经历了很多的波折。

首先一个很粗暴的思路，应该就是用框框遍历，然后标记节点，这个或许也可以做，比如用一些二维树状数组这样的东西，虽然没有尝试。

问题转化思路（正确性待定）

然后看了hint，发现是可以转化问题的：
所有格子能被覆盖到 <=> 每个格子所在行（列）连续为空的长度大于框框宽（高）度

乍一看，似乎是不对的，仔细一看，emmm，好像确实不对啊！！开始懵逼了…
https://leetcode.com/problems/stamping-the-grid/discuss/1865459/Is-hint-correct
反例：

1,1,1,0,0,0
1,1,1,0,0,0
1,1,0,0,0,0
0,0,0,0,1,1
0,0,0,1,1,1
0,0,0,1,1,1
input:
[[1,1,1,0,0,0],[1,1,1,0,0,0],[1,1,0,0,0,0],[0,0,0,0,1,1],[0,0,0,1,1,1],[0,0,0,1,1,1]]
3
3

不过当时没想到，还是写了一个答案：

class Solution:
    def possibleToStamp(self, g: List[List[int]], h: int, w: int) -> bool:
        m, n = len(g), len(g[0])
        mark = [[0 for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if g[i][j] == 1:
                    mark[i][j] = 2
        for i in range(m):
            left = [0] * n
            for j in range(n):
                if g[i][j] == 0:
                    left[j] = left[j - 1] + 1 if j > 0 else 1
            right = 0
            for j in range(n - 1, -1, -1):
                if g[i][j] == 0:
                    if left[j] + right >= w:
                        mark[i][j] += 1
                    right += 1
        for j in range(n):
            top = [0] * m
            for i in range(m):
                if g[i][j] == 0:
                    top[i] = top[i - 1] + 1 if i > 0 else 1
            bottom = 0
            for i in range(m - 1, -1, -1):
                if g[i][j] == 0:
                    if top[i] + bottom >= h:
                        mark[i][j] += 1
                    bottom += 1
        # print(mark)
        return all(x == 2 for x in sum(mark, []))

当然，也没有通过，超时了，可能是O(mn)的常数太大了。
不过可以说下思路：
按照hint所说，计算每个节点所在行的连续空格长度和所在列的连续空格长度。
行和列分开计算，每次需要两遍，记录左边的，然后online处理右边的，上下同理。也算是个比较常规的处理方式吧。其它的就没什么好说的了。

批量区间标记的处理

另一种思路，一开始的想法是，要批量标记框框里的节点太过耗时，需要O(hw)，那么有没有更简便的方式呢？
这里就有一个很trick的方式，把四个角一标，那么prefixSum就是标记的结果啦！！

https://leetcode.com/problems/stamping-the-grid/discuss/1675344/Python-2d-cumulative-sums-explained

例如：

0 0 0 0 0 0                       0 0 0 0 0 0                       
0 1 1 1 0 0                       0 1 0 0 -1 0                       
0 1 1 1 0 0           ==>         0 0 0 0 0 0                       
0 0 0 0 0 0                       0 -1 0 0 1 0                       
0 0 0 0 0 0                       0 0 0 0 0 0

太妙了，太妙了！
有了这个trick，其它的就很粗暴了，题解如下：
基本就是判断这个框框是否能放在当前位置（里边都为0，可以通过psum算出来），能放下，就标记当前框框所在区域。

class Solution:
    def possibleToStamp(self, g: List[List[int]], h: int, w: int) -> bool:
        m, n = len(g), len(g[0])
        def preSumMat(mat):
            m, n = len(mat), len(mat[0])
            acc = [[0 for j in range(n + 1)] for i in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + mat[i - 1][j - 1]
            return acc
        psumG = preSumMat(g)
        valid = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(m - h + 1):
            for j in range(n - w + 1):
                top, bottom, left, right = i, i + h, j, j + w
                if psumG[bottom][right] - psumG[top][right] - psumG[bottom][left] + psumG[top][left] == 0:
                    valid[top][left] += 1
                    valid[top][right] += -1
                    valid[bottom][left] += -1
                    valid[bottom][right] += 1
        psumValid = preSumMat(valid)
        for i in range(m):
            for j in range(n):
                if g[i][j] == 0 and psumValid[i + 1][j + 1] == 0:
                    return False
        return True

精心设计的贪心

这个方法似乎效率并不高，将将能过，有没有更高效的方式呢，看了提交时间分布之后，找到一个更合理的解法。
这个解法本身没什么复杂的，就是判断框框是否能放下，然后标记节点，但是合理的设计遍历顺序以及提前退出，能取得很好的用时表现。

首先计算一个height数组，也就是当前节点上边有多高的连续空格，只要有连续w个不小于h的height，那么就可以放下一个框框。
然后开始遍历每个坐标，看是否满足上述条件，如果满足，则标记这个框框内的所有元素为1，这样可以避免重复标记。这里需要注意几点：

遇到当前height<h或width<w的，直接continue，比较好理解，目前还放不下框框
遍历标记框框内元素的时候，必须是：从右到左，从下到上进行遍历，如此才能保证early break的结果是对的

举个例子为什么这么遍历：

1 0 0
0 0 0
0 0 0
w = 2, h = 2
first fill:
1 1 1
0 1 1
0 0 0
secend fill:
1 1 1
x 1 1
x x 0

第二个标记的时候，要标记三个x所在的位置，只有这样的标记方式才能保证。

完整题解：

class Solution:
    def possibleToStamp(self, g: List[List[int]], h: int, w: int) -> bool:
        m, n = len(g), len(g[0])
        height = [[0 for j in range(n)] for i in range(m)]
        height[0] = [1 - x for x in g[0]]
        for i in range(1, m):
            for j in range(n):
                if g[i][j] == 0:
                    height[i][j] = 1 + height[i - 1][j]
                else:
                    height[i][j] = 0
        for i in range(m):
            validHeightCount = 0
            for j in range(n):
                if height[i][j] < h:
                    validHeightCount = 0
                    continue
                validHeightCount += 1
                if validHeightCount < w:
                    continue
                # loop reverse, early break, column by column first
                for jj in range(j, j - w, -1):
                    if g[i][jj] == 1:
                        break
                    for ii in range(i, i - h, -1):
                        if g[ii][jj] == 1:
                            break
                        g[ii][jj] = 1
        for i in range(m):
            for j in range(n):
                if g[i][j] == 0:
                    return False
        return True