无锡装饰网站建设排名wordpress 开启侧边栏

无锡装饰网站建设排名,wordpress 开启侧边栏,域名注册查询站长工具,做肝病科网站LeetCode 3531 – Count Covered Buildings 题解 给定一个正整数 n 表示一座 n x n 的城市网格,以及一个数组 buildings,其中 buildings[i] [x, y] 表示在坐标 (x, y) 上有一栋建筑,且所有坐标互不相同。leetcode 如果某栋建筑在四个方向上都至少有一栋其他建筑(左、右、上、…LeetCode 3531 – Count Covered Buildings 题解给定一个正整数 n 表示一座 n x n 的城市网格,以及一个数组 buildings,其中 buildings[i] [x, y] 表示在坐标 (x, y) 上有一栋建筑,且所有坐标互不相同。leetcode如果某栋建筑在四个方向上都至少有一栋其他建筑(左、右、上、下),则称这栋建筑是「被覆盖的」。形式化地说,对建筑 (x, y):同一行 x 上,存在列坐标小于 y 的建筑(左边);同一行 x 上,存在列坐标大于 y 的建筑(右边);同一列 y 上,存在行坐标小于 x 的建筑(上边或下边,取决于坐标系约定);同一列 y 上,存在行坐标大于 x 的建筑(与上一个相反方向)。问:共有多少栋建筑是被覆盖的?leetcode朴素直觉:从每栋建筑向四个方向扫一开始很自然的想法是:遍历每一个建筑 (x, y);向左、向右、向上、向下在整个 n x n 网格上「扫」一条线,看看能不能找到其他建筑;如果四个方向都找到了,就把答案加一。这个思路在正确性上其实没问题,因为定义就是这样:四个方向上只要能找到至少一栋建筑就行。问题在于效率。约束中 n 最多可以到 10^5,buildings.length 也可以到 10^5。leetcode如果你真在网格上按行、按列一路扫到边界,最坏情况下:对每栋建筑,向某个方向扫描要走 O(n);有 4 个方向,因此大约 O(4n);一共有 m buildings.length 栋建筑,总复杂度约是 O(m · n)。在 n 和 m 都到 10^5 量级时,O(m · n) 接近 10^10 级别,完全超出可接受范围,这就是面试官会否掉这种方案的原因。换个视角:真正「需要」的信息是什么?关键问题是:判断 (x, y) 是否被覆盖,真的需要在网格上一个格子一个格子地扫吗?观察定义可以发现,只关心「有没有建筑」,而且只在同一行和同一列上:youtube algo对水平方向:是否存在 (x, y_left),使得 y_left y?是否存在 (x, y_right),使得 y_right y?对垂直方向:是否存在 (x_up, y),使得 x_up x?是否存在 (x_down, y),使得 x_down x?换句话说,只要知道:在行 x 里,所有建筑的列坐标的最小值和最大值;在列 y 里,所有建筑的行坐标的最小值和最大值;就可以知道 (x, y) 是否被「夹在中间」。algo youtube核心思路:按行按列维护最小/最大坐标下面是一个非常高效、又很「面试友好」的做法:第一步:按行、按列收集坐标对每一栋建筑 (x, y):在「按行」的结构里,把该行的 y 放进去;在「按列」的结构里,把该列的 x 放进去。可以用两种方式来实现:使用 map 排序,维护每一行/每一列的一个排序后的坐标列表;algo或者更直接地,为每行维护 minY[x] 和 maxY[x],为每列维护 minX[y] 和 maxX[y]。linkedin只维护最小/最大更轻量,这里用这种版本来说明思路。初始化:minY[x] 初始为一个极大值,maxY[x] 初始为一个极小值;minX[y] 和 maxX[y] 同理。遍历所有建筑 (x, y) 时:minY[x] min(minY[x], y);maxY[x] max(maxY[x], y);minX[y] min(minX[y], x);maxX[y] max(maxX[y], x)。youtube linkedin这一趟遍历是 O(m)。直觉上:minY[x] 就是这一行最左边的建筑;maxY[x] 就是这一行最右边的建筑;minX[y] 是这一列最上/下边(取决于坐标系)的建筑;maxX[y] 是这一列最下/上边的建筑。第二步:判断每栋建筑是否「被夹住」再遍历一遍 buildings,对于每个 (x, y),检查:youtube algo左边是否有建筑:minY[x] y;右边是否有建筑:maxY[x] y;上边是否有建筑:minX[y] x;下边是否有建筑:maxX[y] x。如果四个条件全部满足,就说明 (x, y) 在行上被左右夹住、在列上被上下夹住,是一个被覆盖的建筑,答案加一。algo youtube从更直观的角度看:minY[x] y maxY[x] ⇒ 同一行里它不是最左也不是最右,两侧都有建筑。minX[y] x maxX[y] ⇒ 同一列里它不是最上/最下,两侧都有建筑。复杂度分析第一次遍历:更新每行/每列的最小值和最大值,时间 O(m)。algo第二次遍历:对每栋建筑做 O(1) 判断,时间也是 O(m)。algo总时间复杂度O(m),空间复杂度是 O(n) 级别用来存储这些最值信息,非常适合在面试中展示。细节补充:一些边界与剪枝还可以做一个小优化:要在一行里有「左和右」两个方向,至少得有 3 栋建筑;要在一列里有「上和下」两个方向,同样至少得有 3 栋建筑。algo所以在第二次遍历建筑时,可以:统计每行 cntRow[x] 和每列 cntCol[y] 的建筑数量;如果 cntRow[x] 3 或 cntCol[y] 3,这栋建筑肯定不可能被覆盖,可以直接跳过判断。algo这个剪枝在数据比较分散时很划算,也能给面试官展示你对条件的深入理解。参考代码示例(伪代码风格)下面是接近实际代码的伪代码结构,和上面描述一致:function countCoveredBuildings(n, buildings): // 假设行和列都是 1..n INF ∞ // 用数组或哈希表都可以 minY array[1..n] filled with INF maxY array[1..n] filled with -INF minX array[1..n] filled with INF maxX array[1..n] filled with -INF cntRow array[1..n] filled with 0 cntCol array[1..n] filled with 0 // 第一次遍历:更新最值和计数 for (x, y) in buildings: minY[x] min(minY[x], y) maxY[x] max(maxY[x], y) minX[y] min(minX[y], x) maxX[y] max(maxX[y], x) cntRow[x] 1 cntCol[y] 1 ans 0 // 第二次遍历:判断是否覆盖 for (x, y) in buildings: // 剪枝:行或列少于 3 栋,直接不可能 if cntRow[x] 3 or cntCol[y] 3: continue if minY[x] y and y maxY[x] and minX[y] x and x maxX[y]: ans 1 return ans这一解法的核心在于:把「是否有建筑」抽象成「是否在最小值和最大值之间」,避免对网格做任何无谓的扫描。linkedin youtube