题目描述
思路解析动画文字版
记牢这一句:左上角的判据是左边和上边都不是农场。因为每个矩形组只有它真正的左上角这一格能同时满足这两条,所以每个组只会被触发一次,不重也不漏。定位到左上角后,先下探再右探,矩形的对角就出来了。下面从第 0 行第 0 列开始扫。
整张 land · 四个矩形待框定：先把整张图看清楚。蓝色格子是森林 0,中性色格子是农场 1。眼睛能看出四块农场:左上单格、第 0 行的横条、左下的方块、右下的竖条。但代码不会一眼看全局,它是一格一格从左到右、从上到下扫过去的,靠判左上角来发现每一个组。已记录的农场组数现在是 0。
扫到 (0,0) · 判定左上角：外层从 (0,0) 开始扫,这是农场。它在第 0 行第 0 列,左边和上边都出了边界、都不是农场,两条都满足,所以它就是一个农场组的左上角。抓住它,开始向下、向右扩,把这个组的矩形框出来。
组 A 向下探 · 下一行是森林：先沿着第 0 列往下探。看下一行 (1,0) 是森林 0,下不去了,所以这个组的最下行就停在第 0 行,r2 等于 0。这一列只有它自己一格高。
组 A 向右探 · 右邻是森林,记录 [0,0,0,0]：再从最下行往右探。右边 (0,1) 是森林 0,右不动了,最右列也停在第 0 列。左上角 (0,0),右下角 (0,0),这是个单格组,记下 [0,0,0,0],整块涂绿。农场组数变成 1。
扫到 (0,1) · 森林,跳过：继续往右扫到 (0,1),它是森林 0,不是农场,直接跳过。扫描只在农场格上才可能触发判定。
扫到 (0,2) · 判定左上角：扫到 (0,2),这是农场。它左边 (0,1) 是森林,上边出了边界,左、上都不是农场,判定成立,它是一个新组的左上角。开始下探、右探。
组 B 向下探 · 下一行是森林：沿第 2 列往下,下一行 (1,2) 是森林 0,下不去,最下行停在第 0 行,r2 等于 0。这个组也只有一行高。
组 B 向右探 · 右邻是农场,继续：从第 0 行往右探,右边 (0,3) 还是农场,能扩,最右列推进到第 3 列,c2 先记成 3。再看它右边还有没有农场。
组 B 向右探停 · 记录 [0,2,0,3]：再往右 (0,4) 是森林 0,右探到头,最右列定在第 3 列。左上角 (0,2),右下角 (0,3),这是个横着的两格组,记下 [0,2,0,3],整条涂绿。农场组数到 2。
扫到 (0,3) · 左邻是农场,跳过：扫描继续走到 (0,3)。它虽然是农场,但左边 (0,2) 也是农场,说明它不是最左那格,已经属于刚才框好的组 B。判据里左邻是农场就跳过,不会重新开一个组。这正是不重复的关键。
扫第 1 行 · 整行都是森林：第 0 行扫完,进到第 1 行。这一行 (1,0) 到 (1,4) 全是森林 0,一个农场都没有,整行都不会触发判定,快速略过。农场组之间隔着的,正是这样的森林带。
扫到 (2,0) · 判定左上角：进到第 2 行,扫到 (2,0),它是农场。它在第 0 列没有左邻,上边 (1,0) 是森林,左、上都不是农场,判定成立,又一个新组的左上角。这次的组要大一些,认真下探。
组 C 向下探 · 下一行还是农场：沿第 0 列往下,下一行 (3,0) 还是农场,能下去,最下行推进到第 3 行,r2 记成 3。继续看还能不能再往下。
组 C 向下探停 · 触底出界：再往下就是第 4 行,已经出了矩阵的下边界,下探到此为止,最下行定在第 3 行。注意接下来的右探要从这一最下行、也就是第 3 行出发,而不是从起点那行。
组 C 向右探(第 3 行)· 右邻是农场：从最下行第 3 行往右探。右边 (3,1) 是农场,能扩,最右列推到第 1 列,c2 记成 1。因为组是矩形,底行的宽度就是整个组的宽度,所以从底行量最省事。
组 C 向右探停 · 记录 [2,0,3,1]：再往右 (3,2) 是森林 0,右探到头,最右列定在第 1 列。左上角 (2,0),右下角 (3,1),这是个 2 乘 2 的方块,记下 [2,0,3,1],整块涂绿。农场组数到 3。你看,虽然只走了一列加一行,整个矩形的四角就都定出来了。
扫到 (2,1) · 左邻是农场,跳过：扫描回到第 2 行接着走,来到 (2,1)。它是农场,但左边 (2,0) 也是农场,它属于刚框好的组 C,不是左上角,跳过。组 C 的其余格子都会这样被判为同组内部而略过。
扫到 (2,3) · 判定左上角：第 2 行继续,扫到 (2,3),农场。它左边 (2,2) 是森林,上边 (1,3) 也是森林,左、上都不是农场,最后一个新组的左上角就是它。
组 D 向下探 · 下一行还是农场：沿第 3 列往下,下一行 (3,3) 还是农场,下去,最下行到第 3 行,r2 等于 3。再往下出界,下探停在这里。
组 D 向右探停 · 记录 [2,3,3,3]：从第 3 行往右探,右边 (3,4) 是森林 0,右不动,最右列停在第 3 列。左上角 (2,3),右下角 (3,3),这是个竖着的两格组,记下 [2,3,3,3],涂绿。农场组数到 4,四个组都框好了。
扫到 (3,0) · 上邻是农场,跳过：扫到第 3 行的 (3,0)。它是农场,左边没有邻居,但上边 (2,0) 是农场,说明它不是最上那格,属于组 C。上邻是农场就跳过。判据把左和上都管住,才能保证只有真正的左上角这一格会触发。
扫到 (3,3) · 上邻是农场,跳过：再看 (3,3),它是农场,上边 (2,3) 也是农场,属于刚框好的组 D,同样跳过。剩下的格子要么是森林、要么是同组内部,都不会再开新组。
回放 · 四个农场组全部框定：整张图扫完了。四个绿色矩形就是四个农场组:单格 [0,0,0,0]、横条 [0,2,0,3]、方块 [2,0,3,1]、竖条 [2,3,3,3]。全程没有用递归、没有开访问数组,只靠判左上角加两次直线扩边界,就把每个矩形的对角坐标都拿到了。这就是最终答案,共 4 组。
边界想清:全森林返回空、单格农场记 [0,0,0,0]、整块方块只被左上角 (0,0) 触发一次得到 [0,0,1,1]。
面试重点:判左上角加两次直线扩边界、也可退回洪水填充或并查集求外接矩形、本解空间 O(1) 胜在不递归不开表。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findFarmland(self, land: List[List[int]]) -> List[List[int]]: m, n = len(land), len(land[0]) ans = [] for i in range(m): for j in range(n): if ( land[i][j] == 0 or (j > 0 and land[i][j - 1] == 1) or (i > 0 and land[i - 1][j] == 1) ): continue x, y = i, j while x + 1 < m and land[x + 1][j] == 1: x += 1 while y + 1 < n and land[x][y + 1] == 1: y += 1 ans.append([i, j, x, y]) return ans复杂度
- 时间：O(m·n)，m 行 n 列共 m 乘 n 个格子。外层把每个格子扫一遍;向下、向右扩边界时,每个农场格总共只会被某个组的扩展经过常数次,所有扩展加起来不超过农场格总数。合计随格子总数线性增长
- 空间：O(1)，按峰值算,不计返回的答案数组。没有递归栈、没有额外访问表,只用了 i,j,x,y 几个下标变量。这正是它比洪水填充省的地方:洪水填充要么开访问数组、要么吃递归栈,都是 O(m·n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问不利用矩形性质,还能怎么做?
追问为什么这个解法空间能做到 O(1)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格游戏
LeetCode 2017 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题