阅读视图

发现新文章，点击刷新页面。

统计行列的最小值和最大值（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年4月27日 12:46

分析

如果一个点在同一行的最左边，那么它左边没有点；如果一个点在同一行的最右边，那么它右边没有点。

如果一个点在同一列的最上边，那么它上边没有点；如果一个点在同一列的最下边，那么它下边没有点。

反之，如果一个点不在同一行的最左边也不在最右边，那么这个点左右都有点；如果一个点不在同一列的最上边也不在最下边，那么这个点上下都有点。

算法

记录同一行的最小横坐标和最大横坐标，同一列的最小纵坐标和最大纵坐标。

对于每个建筑 $(x,y)$，如果 $x$ 在这一行的最小值和最大值之间（不能相等），$y$ 在这一列的最小值和最大值之间（不能相等），那么答案加一。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        row_min = [n + 1] * (n + 1)
        row_max = [0] * (n + 1)
        col_min = [n + 1] * (n + 1)
        col_max = [0] * (n + 1)

        for x, y in buildings:
            # 手写 min max 更快
            if x < row_min[y]: row_min[y] = x
            if x > row_max[y]: row_max[y] = x
            if y < col_min[x]: col_min[x] = y
            if y > col_max[x]: col_max[x] = y

        ans = 0
        for x, y in buildings:
            if row_min[y] < x < row_max[y] and col_min[x] < y < col_max[x]:
                ans += 1
        return ans

###java

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        int[] rowMin = new int[n + 1];
        int[] rowMax = new int[n + 1];
        int[] colMin = new int[n + 1];
        int[] colMax = new int[n + 1];
        Arrays.fill(rowMin, n + 1);
        Arrays.fill(colMin, n + 1);

        for (int[] p : buildings) {
            int x = p[0], y = p[1];
            rowMin[y] = Math.min(rowMin[y], x);
            rowMax[y] = Math.max(rowMax[y], x);
            colMin[x] = Math.min(colMin[x], y);
            colMax[x] = Math.max(colMax[x], y);
        }

        int ans = 0;
        for (int[] p : buildings) {
            int x = p[0], y = p[1];
            if (rowMin[y] < x && x < rowMax[y] && colMin[x] < y && y < colMax[x]) {
                ans++;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        vector<int> row_min(n + 1, INT_MAX), row_max(n + 1);
        vector<int> col_min(n + 1, INT_MAX), col_max(n + 1);
        for (auto& p : buildings) {
            int x = p[0], y = p[1];
            row_min[y] = min(row_min[y], x);
            row_max[y] = max(row_max[y], x);
            col_min[x] = min(col_min[x], y);
            col_max[x] = max(col_max[x], y);
        }

        int ans = 0;
        for (auto& p : buildings) {
            int x = p[0], y = p[1];
            if (row_min[y] < x && x < row_max[y] && col_min[x] < y && y < col_max[x]) {
                ans++;
            }
        }
        return ans;
    }
};

###go

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
type pair struct{ min, max int }
row := make([]pair, n+1)
col := make([]pair, n+1)
for i := 1; i <= n; i++ {
row[i].min = math.MaxInt
col[i].min = math.MaxInt
}

add := func(m []pair, x, y int) {
m[y].min = min(m[y].min, x)
m[y].max = max(m[y].max, x)
}
isInner := func(m []pair, x, y int) bool {
return m[y].min < x && x < m[y].max
}

for _, p := range buildings {
x, y := p[0], p[1]
add(row, x, y) // x 加到 row[y] 中
add(col, y, x) // y 加到 col[x] 中
}

for _, p := range buildings {
x, y := p[0], p[1]
if isInner(row, x, y) && isInner(col, y, x) {
ans++
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n+m)$，其中 $m$ 是 $\textit{buildings}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

脑筋急转弯（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年6月8日 12:06

题目说：用计算机 $j$ 解锁计算机 $i$ 的前提是 $j<i$ 且 $\textit{complexity}[j] < \textit{complexity}[i]$。

观察：

一开始就解锁的只有计算机 $0$。
第一轮，被 $0$ 解锁的计算机（记作集合 $A$），密码复杂度比 $\textit{complexity}[0]$ 大。
第二轮，被集合 $A$ 中的计算机解锁的计算机（记作集合 $B$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
第三轮，被集合 $B$ 中的计算机解锁的计算机（记作集合 $C$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
依此类推，所有被解锁的计算机的密码复杂度都要比 $\textit{complexity}[0]$ 大。

定理：当且仅当计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，才能解锁所有计算机。

充分性：如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，根据题意，仅用计算机 $0$ 便可解锁所有计算机。

必要性：如果可以解锁所有的计算机，那么计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大。考虑其逆否命题，即如果在计算机 $0$ 的右边存在计算机 $A$，满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，那么不可能解锁计算机 $A$，更不可能解锁所有计算机。为了解锁计算机 $A$，我们需要在其左边找比 $\textit{complexity}[i]$ 更小的计算机。不断往左找，计算机的密码复杂度只会更小，直到找到一台被计算机 $0$ 解锁的计算机 $B$。$B$ 的密码复杂度必须比 $\textit{complexity}[0]$ 大，但为了能解锁计算机 $A$，$B$ 的密码复杂度又要 $< \textit{complexity}[i] \le \textit{complexity}[0]$，矛盾，所以不可能解锁计算机 $A$。

根据定理，如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，那么我们可以按照任意顺序解锁这 $n-1$ 台计算机，方案数为 $n-1$ 个不同物品的全排列个数，即

$$
(n-1)!
$$

注意取模。关于模运算的知识点，见模运算的世界：当加减乘除遇上取模。