Rust）

LeetCode 每日一题题解

endlesscheng

2025年8月22日 21:53

由于 $x + (-x) = 0$ 恒成立，可以把 $1$ 和 $-1$，$2$ 和 $-2$，$3$ 和 $-3$ 等成对添加到答案中。如果 $n$ 是奇数，就再加个 $0$。

方便编程实现的一种构造方案如下。其中 $m = \left\lfloor\dfrac{n}{2}\right\rfloor$。

当 $n$ 为偶数时：

$$
[1,2,\dots,m-1,m,-1,-2,\dots,-(m-1),-m]
$$

当 $n$ 为奇数时：

$$
[1,2,\dots,m-1,m,-1,-2,\dots,-(m-1),-m,0]
$$

###py

class Solution:
    def sumZero(self, n: int) -> List[int]:
        a = [0] * n
        m = n // 2
        for i in range(m):
            a[i] = i + 1
            a[i + m] = -i - 1
        return a

###py

class Solution:
    def sumZero(self, n: int) -> List[int]:
        m = n // 2
        if n % 2:
            return list(range(-m, m + 1))
        return list(range(-m, 0)) + list(range(1, m + 1))

###java

class Solution {
    public int[] sumZero(int n) {
        int[] a = new int[n];
        int m = n / 2;
        for (int i = 0; i < m; i++) {
            a[i] = i + 1;
            a[i + m] = -i - 1;
        }
        return a;
    }
}

###cpp

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> a(n);
        int m = n / 2;
        for (int i = 0; i < m; i++) {
            a[i] = i + 1;
            a[i + m] = -i - 1;
        }
        return a;
    }
};

###c

int* sumZero(int n, int* returnSize) {
    int* a = calloc(n, sizeof(int));
    int m = n / 2;
    for (int i = 0; i < m; i++) {
        a[i] = i + 1;
        a[i + m] = -i - 1;
    }
    *returnSize = n;
    return a;
}

###go

func sumZero(n int) []int {
a := make([]int, n)
m := n / 2
for i := range m {
a[i] = i + 1
a[i+m] = -i - 1
}
return a
}

###js

var sumZero = function(n) {
    const a = Array(n).fill(0);
    const m = Math.floor(n / 2);
    for (let i = 0; i < m; i++) {
        a[i] = i + 1;
        a[i + m] = -i - 1;
    }
    return a;
};

###rust

impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut a = vec![0; n];
        let m = n / 2;
        for i in 0..m {
            a[i] = i as i32 + 1;
            a[i + m] = -a[i];
        }
        a
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

专题训练

见下面贪心与思维题单的「六、构造题」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

从 O(log U) 到 O(1)（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年3月23日 13:11

分析

$a$ 除以 $4$ 下取整等价于 $a$ 右移 $2$ 位。所以把一个长为 $m$ 的二进制数变成 $0$，需要操作 $\left\lceil\dfrac{m}{2}\right\rceil$ 次。

例如 $l=1$，$r=5$，如果每次操作只把一个数右移 $2$ 位，那么 $1$ 到 $5$ 每个数的操作次数分别为

$$
\textit{ops}=[1,1,1,2,2]
$$

本题一次可以操作两个数，问题等价于：

每次操作把 $\textit{ops}$ 中的两个数都减去 $1$，问：要让 $\textit{ops}$ 中没有正数，至少要操作多少次？

分析：设 $\textit{tot}=\sum \textit{ops}[i]$，$\textit{mx}=\max(\textit{ops})$。假如每次可以把 $\textit{tot}$ 减少 $2$，那么把 $\textit{tot}$ 减少到 $\le 0$，至少要操作 $\left\lceil\dfrac{\textit{tot}}{2}\right\rceil$ 次。但如果 $\textit{mx}$ 很大，操作次数就等于 $\textit{mx}$（每次操作选 $\textit{mx}$ 和另一个数）。

定理：最少操作次数为

$$
\max\left(\left\lceil\dfrac{\textit{tot}}{2}\right\rceil, \textit{mx}\right)
$$

证明+具体操作方案。

本题由于 $\textit{nums}$ 中的数字是连续整数，相邻数字的操作次数至多相差 $1$。

例如两个数的情况 $\textit{ops}=[x-1,x]$，得到 $\textit{mx}=x$，$\textit{tot} = 2x-1$。由于 $\left\lceil\dfrac{2x-1}{2}\right\rceil = x$，所以 $\textit{mx} \le \left\lceil\dfrac{\textit{tot}}{2}\right\rceil$ 成立。推广到更多元素的情况，设最大值为 $\textit{mx}=x$，其余元素不超过 $x$，当元素增多时，$\textit{tot}$ 更大，$\textit{mx} \le \left\lceil\dfrac{\textit{tot}}{2}\right\rceil$ 更加成立。

所以本题

$$
\textit{mx} \le \left\lceil\dfrac{\textit{tot}}{2}\right\rceil
$$

恒成立。

所以

$$
\max\left(\left\lceil\dfrac{\textit{tot}}{2}\right\rceil, \textit{mx}\right) = \left\lceil\dfrac{\textit{tot}}{2}\right\rceil
$$

算出了 $\textit{tot}$，就算出了答案。

公式推导

定义 $f(n)$ 为 $[1,n]$ 中的单个数的操作次数之和。

设 $n$ 的二进制长度为 $m$。按照 $[1,n]$ 中的数字的二进制长度，分组计算：

对于长为 $i$ 的二进制数（其中 $1\le i\le m-1$），最小是 $2^{i-1}$，最大是 $2^i-1$，共有 $2^{i-1}$ 个，每个需要操作 $\left\lceil\dfrac{i}{2}\right\rceil$ 次。
对于长为 $m$ 的二进制数，最小是 $2^{m-1}$，最大是 $n$，共有 $n+1-2^{m-1}$ 个，每个需要操作 $\left\lceil\dfrac{m}{2}\right\rceil$ 次。

两部分累加，得

$$
f(n) = \sum_{i=1}^{m-1} \left\lceil\dfrac{i}{2}\right\rceil 2^{i-1} + \left\lceil\dfrac{m}{2}\right\rceil(n+1-2^{m-1})
$$

由于 $[l,r]$ 可以拆分成 $[1,r]$ 减去 $[1,l-1]$，所以 $[l,r]$ 中的单个数的操作次数之和为

$$
\textit{tot} = f(r) - f(l-1)
$$

每次操作至多两个数，操作次数为

$$
\left\lceil\dfrac{f(r) - f(l-1)}{2}\right\rceil = \left\lfloor\dfrac{ f(r) - f(l-1) + 1}{2}\right\rfloor
$$

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

优化前

###py

# 返回 [1,n] 的单个元素的操作次数之和
def f(n: int) -> int:
    m = n.bit_length()
    res = sum((i + 1) // 2 << (i - 1) for i in range(1, m))
    return res + (m + 1) // 2 * (n + 1 - (1 << m >> 1))

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        return sum((f(r) - f(l - 1) + 1) // 2 for l, r in queries)

###java

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            ans += (f(q[1]) - f(q[0] - 1) + 1) / 2;
        }
        return ans;
    }

    // 返回 [1,n] 的单个元素的操作次数之和
    private long f(int n) {
        int m = 32 - Integer.numberOfLeadingZeros(n);
        long res = 0;
        for (int i = 1; i < m; i++) {
            res += (long) (i + 1) / 2 << (i - 1);
        }
        return res + (long) (m + 1) / 2 * (n + 1 - (1 << m >> 1));
    }
}

###cpp

class Solution {
    // 返回 [1,n] 的单个元素的操作次数之和
    long long f(int n) {
        int m = bit_width((uint32_t) n);
        long long res = 0;
        for (int i = 1; i < m; i++) {
            res += 1LL * (i + 1) / 2 << (i - 1);
        }
        return res + 1LL * (m + 1) / 2 * (n + 1 - (1 << m >> 1));
    }

public:
    long long minOperations(vector<vector<int>>& queries) {
        long long ans = 0;
        for (auto& q : queries) {
            ans += (f(q[1]) - f(q[0] - 1) + 1) / 2;
        }
        return ans;
    }
};

###go

// 返回 [1,n] 的单个元素的操作次数之和
func f(n int) (res int) {
m := bits.Len(uint(n))
for i := 1; i < m; i++ {
res += (i + 1) / 2 << (i - 1)
}
return res + (m+1)/2*(n+1-1<<m>>1)
}

func minOperations(queries [][]int) int64 {
ans := 0
for _, q := range queries {
ans += (f(q[1]) - f(q[0]-1) + 1) / 2
}
return int64(ans)
}

复杂度分析

时间复杂度：$\mathcal{O}(q\log U)$，其中 $q$ 是 $\textit{queries}$ 的长度，$U$ 是 $r$ 的最大值。每个询问需要 $\mathcal{O}(\log U)$ 的时间。
空间复杂度：$\mathcal{O}(1)$。

化简公式

$\mathcal{O}(1)$ 计算 $f(n)$。

设 $n$ 的二进制长度为 $m$。设 $k$ 为小于 $m$ 的最大偶数。

上面代码的循环，把二进制长为 $1,2$ 的分成一组（每个数操作 $1$ 次），长为 $3,4$ 的分成一组（每个数操作 $2$ 次），长为 $5,6$ 的分成一组（每个数操作 $3$ 次）……依此类推，累加得

$$
(2^2-2^0)\cdot 1 + (2^4-2^2)\cdot 2 + \cdots + (2^k-2^{k-2})\cdot \dfrac{k}{2}
$$

利用错位相减法（详见视频讲解），上式可化简为

$$
k\cdot 2^{k-1} - \dfrac{2^k-1}{3}
$$

对于长为 $[k+1,m]$ 的二进制数，最小是 $2^k$，最大是 $n$，共有 $n+1-2^k$ 个，每个需要操作 $\left\lceil\dfrac{m}{2}\right\rceil$ 次。

相加得

$$
f(n) = k\cdot 2^{k-1} - \dfrac{2^k-1}{3} + \left\lceil\dfrac{m}{2}\right\rceil(n+1-2^k)
$$

代码实现时，如果 $k=0$，没法左移 $k-1=-1$ 位。可以改为先左移 $k$ 位，再右移一位，这样无需特判 $k=0$ 的情况。

###py

def f(n: int) -> int:
    if n == 0:
        return 0
    m = n.bit_length()
    k = (m - 1) // 2 * 2
    res = (k << k >> 1) - (1 << k) // 3  # -1 可以省略
    return res + (m + 1) // 2 * (n + 1 - (1 << k))

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        return sum((f(r) - f(l - 1) + 1) // 2 for l, r in queries)

###java

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            ans += (f(q[1]) - f(q[0] - 1) + 1) / 2;
        }
        return ans;
    }

    private long f(int n) {
        int m = 32 - Integer.numberOfLeadingZeros(n);
        int k = (m - 1) / 2 * 2;
        long res = ((long) k << k >> 1) - (1 << k) / 3; // -1 可以省略
        return res + (long) (m + 1) / 2 * (n + 1 - (1 << k));
    }
}

###cpp

class Solution {
    long long f(int n) {
        int m = bit_width((uint32_t) n);
        int k = (m - 1) / 2 * 2;
        long long res = (1LL * k << k >> 1) - (1 << k) / 3; // -1 可以省略
        return res + 1LL * (m + 1) / 2 * (n + 1 - (1 << k));
    }

public:
    long long minOperations(vector<vector<int>>& queries) {
        long long ans = 0;
        for (auto& q : queries) {
            ans += (f(q[1]) - f(q[0] - 1) + 1) / 2;
        }
        return ans;
    }
};

###go

func f(n int) int {
m := bits.Len(uint(n))
k := (m - 1) / 2 * 2
res := k<<k>>1 - 1<<k/3 // -1 可以省略
return res + (m+1)/2*(n+1-1<<k)
}

func minOperations(queries [][]int) int64 {
ans := 0
for _, q := range queries {
ans += (f(q[1]) - f(q[0]-1) + 1) / 2
}
return int64(ans)
}

复杂度分析

时间复杂度：$\mathcal{O}(q)$，其中 $q$ 是 $\textit{queries}$ 的长度。每个询问只需 $\mathcal{O}(1)$ 时间。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面贪心题单的「§1.8 相邻不同」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

上下界分析 + 枚举答案（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2023年6月25日 12:07

转化

假设我们操作了 $k$ 次，此时 $\textit{num}_1$ 变成 $\textit{num}_1 - \textit{num}_2\cdot k$ 再减去 $k$ 个 $2^i$。

能否把 $\textit{num}_1$ 变成 $0$，等价于：

能否把 $\textit{num}_1 - \textit{num}_2\cdot k$ 拆分成恰好 $k$ 个 $2$ 的幂之和？

在示例 1 中，$k=3$ 时 $\textit{num}_1 - \textit{num}_2\cdot k = 9$，我们可以把 $9$ 拆分成 $4+4+1$，这三个数都是 $2$ 的幂。

上下界分析

设 $x=\textit{num}_1 - \textit{num}_2\cdot k$。

为了判断能否把 $x$ 拆分成恰好 $k$ 个 $2$ 的幂之和，我们可以先做上下界分析：

上界：求出 $x$ 最多可以拆分出 $\textit{high}$ 个 $2$ 个幂。
下界：求出 $x$ 最少可以拆分出 $\textit{low}$ 个 $2$ 个幂。

由于一个 $2^i$ 可以分解成两个 $2^{i-1}$，而 $2^{i-1}$ 又可以继续分解为 $2^{i-2}$，所以分解出的 $2$ 的幂的个数可以是 $[\textit{low},\textit{high}]$ 中的任意整数。$k$ 只要在这个范围中，那么分解方案就是存在的。

上界：由于 $2$ 的幂最小是 $1$，所以 $x$ 最多可以拆分出 $x$ 个 $2$ 个幂（$x$ 个 $1$）。
下界：$x$ 的二进制中的 $1$ 的个数。比如 $x$ 的二进制为 $10110$，至少要拆分成 $3$ 个 $2$ 的幂，即 $10000+100+10$。

枚举 k

暴力的想法是，从小到大枚举 $k=1,2,3,\ldots$ 计算 $x=\textit{num}_1 - \textit{num}_2\cdot k$，判断 $k$ 是否满足上下界（在区间中）。这样做是否会超时？$k$ 最大枚举到多少呢？

对于上界，即 $k\le x = \textit{num}_1 - \textit{num}_2\cdot k$，变形得 $k\cdot (\textit{num}_2+1)\le \textit{num}_1$。

如果 $\textit{num}_2 + 1\le 0$，由于题目保证 $\textit{num}_1\ge 1$，上式恒成立。
如果 $\textit{num}_2 + 1> 0$，那么 $k\le \dfrac{\textit{num}_1}{\textit{num}_2+1}$。

对于下界，定义 $\text{popcount}(x)$ 为 $x$ 的二进制中的 $1$ 的个数，我们要满足 $k\ge \text{popcount}(x)$。粗略估计一下，当 $k=60$ 时，在本题数据范围下，当 $\textit{num}_1=10^9$，$\textit{num}_2 = -10^9$ 时 $x$ 最大，为 $61\times 10^9$，二进制长度只有 $36$。由于 $\text{popcount}(x)$ 不会超过 $x$ 的二进制长度，所以此时 $k$ 一定满足下界。所以本题的枚举次数其实很小，暴力枚举不会超时。

综上所述，在枚举 $k=1,2,3,\ldots$ 的过程中：

如果 $k > \textit{num}_1 - \textit{num}_2\cdot k$，不满足上界。那么对于更大的 $k$，同样不满足上界，此时可以退出循环，返回 $-1$。
否则，如果 $k$ 满足下界，返回 $k$。
否则，继续枚举 $k$。

视频讲解（第二题）

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in count(1):  # 枚举 k=1,2,3,...
            x = num1 - num2 * k
            if k > x:
                return -1
            if k >= x.bit_count():
                return k

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        for (long k = 1; k <= num1 - num2 * k; k++) {
            if (k >= Long.bitCount(num1 - num2 * k)) {
                return (int) k;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        for (long long k = 1; k <= num1 - num2 * k; k++) {
            if (k >= popcount((uint64_t) num1 - num2 * k)) {
                return k;
            }
        }
        return -1;
    }
};

int makeTheIntegerZero(int num1, int num2) {
    for (long long k = 1; k <= num1 - num2 * k; k++) {
        if (k >= __builtin_popcountll(num1 - num2 * k)) {
            return k;
        }
    }
    return -1;
}

func makeTheIntegerZero(num1, num2 int) int {
for k := 1; k <= num1-num2*k; k++ {
if k >= bits.OnesCount(uint(num1-num2*k)) {
return k
}
}
return -1
}

var makeTheIntegerZero = function(num1, num2) {
    for (let k = 1; k <= num1 - num2 * k; k++) {
        if (k >= bitCount64(num1 - num2 * k)) {
            return k;
        }
    }
    return -1;
};

function bitCount64(i) {
    return bitCount32(Math.floor(i / 0x100000000)) + bitCount32(i >>> 0);
}

function bitCount32(i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

impl Solution {
    pub fn make_the_integer_zero(num1: i32, num2: i32) -> i32 {
        for k in 1.. {
            let x = num1 as i64 - num2 as i64 * k;
            if k > x {
                return -1;
            }
            if k as u32 >= x.count_ones() {
                return k as _;
            }
        }
        unreachable!()
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(f^{-1}(\textit{num}_1+|\textit{num}_2|))$，其中 $f^{-1}(x)$ 是 $f(x)=\dfrac{2^x}{x}$ 的反函数，略大于 $\log_2 x$。在本题的数据范围下，$k\le 36$。
空间复杂度：$\mathcal{O}(1)$。

注：关于这个反函数的研究，见朗伯 W 函数（Lambert W function）。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

计算绝对值（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年4月13日 12:27

时间等于距离除以速度，由于两人速度相同，转化成比较两人到第三人的距离。

设 $a=|x-z|$，$b=|y-z|$。

根据题意：

如果 $a=b$，返回 $0$。
如果 $a<b$，返回 $1$。
如果 $a>b$，返回 $2$。

写法一

###py

class Solution:
    def findClosest(self, x: int, y: int, z: int) -> int:
        a = abs(x - z)
        b = abs(y - z)
        if a == b:
            return 0
        return 1 if a < b else 2

###java

class Solution {
    public int findClosest(int x, int y, int z) {
        int a = Math.abs(x - z);
        int b = Math.abs(y - z);
        return a == b ? 0 : a < b ? 1 : 2;
    }
}

###cpp

class Solution {
public:
    int findClosest(int x, int y, int z) {
        int a = abs(x - z);
        int b = abs(y - z);
        return a == b ? 0 : a < b ? 1 : 2;
    }
};

###c

int findClosest(int x, int y, int z) {
    int a = abs(x - z);
    int b = abs(y - z);
    return a == b ? 0 : a < b ? 1 : 2;
}

###go

func findClosest(x, y, z int) int {
a := abs(x - z)
b := abs(y - z)
if a == b {
return 0
}
if a < b {
return 1
}
return 2
}

func abs(x int) int { if x < 0 { return -x }; return x }

###go

var state = [3]int{1, 0, 2}

func findClosest(x, y, z int) int {
a := abs(x - z)
b := abs(y - z)
return state[cmp.Compare(a, b)+1]
}

func abs(x int) int { if x < 0 { return -x }; return x }

###js

var findClosest = function(x, y, z) {
    const a = Math.abs(x - z);
    const b = Math.abs(y - z);
    return a === b ? 0 : a < b ? 1 : 2;
};

###rust

impl Solution {
    pub fn find_closest(x: i32, y: i32, z: i32) -> i32 {
        let a = (x - z).abs();
        let b = (y - z).abs();
        if a == b { 0 } else if a < b { 1 } else { 2 }
    }
}

写法二

部分语言可以利用 $\texttt{bool}$ 自动转成 $\texttt{int}$ 的特性简化代码逻辑。

###py

class Solution:
    def findClosest(self, x: int, y: int, z: int) -> int:
        a = abs(x - z)
        b = abs(y - z)
        return (a > b) << 1 | (a < b)

###cpp

class Solution {
public:
    int findClosest(int x, int y, int z) {
        int a = abs(x - z);
        int b = abs(y - z);
        return (a > b) << 1 | (a < b);
    }
};

###c

int findClosest(int x, int y, int z) {
    int a = abs(x - z);
    int b = abs(y - z);
    return (a > b) << 1 | (a < b);
}

###js

var findClosest = function(x, y, z) {
    const a = Math.abs(x - z);
    const b = Math.abs(y - z);
    return (a > b) << 1 | (a < b);
};

复杂度分析

时间复杂度：$\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

利用排序简化问题（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2024年2月4日 09:21

设矩形的左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$。

根据题意，合法矩形需要满足如下三个要求：

$x_1\le x_2$。
$y_1\ge y_2$。
矩形内部或边界上没有其他点。

为方便计算，先把 $\textit{points}$ 按照横坐标从小到大排序（横坐标相同呢？后面会说明）。排序后，第一个要求在枚举时自动成立。

然后外层循环枚举 $\textit{points}[i] = (x_1,y_1)$；内层循环从 $i+1$ 开始，枚举 $\textit{points}[j] = (x_2,y_2)$，跳过 $y_2 > y_1$ 的点。这样就满足了第二个要求。

最后来处理第三个要求，其等价于：

对于下标在闭区间 $[i+1,j-1]$ 中的每个点，纵坐标要么大于 $y_1$，要么小于 $y_2$。如果不满足，那么这个点就在矩形内部或边界上了。

纵坐标大于 $y_1$ 的点，我们已经跳过了，所以只需满足纵坐标小于 $y_2$。

枚举到 $\textit{points}[j] = (x_2,y_2)$ 时，之前遍历过的点，纵坐标都必须小于 $y_2$。难道要再遍历一遍 $[i+1,j-1]$？不需要，只要这些点的纵坐标的最大值小于 $y_2$，那么这些点的纵坐标就都小于 $y_2$（$\mathcal{O}(1)$ 时间获取 $\mathcal{O}(n)$ 信息）。所以只需维护遍历过的点的纵坐标的最大值 $\textit{maxY}$。如果发现 $y_2> \textit{maxY}$，就找到了一个合法矩形，把答案加一。

最后来说，对于横坐标相同的点，要怎么处理。

比如 $\textit{points} = [(1,3),(1,2),(1,1)]$，其中有两个满足要求的矩形：$(1,3)$ 为左上角，$(1,2)$ 为右下角的矩形；$(1,2)$ 为左上角，$(1,1)$ 为右下角的矩形。注意 $(1,3)$ 为左上角，$(1,1)$ 为右下角的矩形包含 $(1,2)$，不满足要求。

由于内层循环中的 $j$ 是从 $i+1$ 开始枚举的，所以在横坐标相同时，要按照纵坐标从大到小排序。这也保证了横坐标相同时，我们总是会先遍历到纵坐标更大的点。在上面的例子中，遍历到 $(1,1)$ 之前，一定会先遍历到 $(1,2)$。这样对于 $(1,3)$ 为左上角，$(1,1)$ 为右下角的矩形，我们就能正确地判断出这个矩形是不合法的。

优化：如果在循环中发现 $\textit{maxY} = y_1$，那么不存在满足要求的 $y_2$，此时可以退出循环。

视频讲解第四题。

###py

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda p: (p[0], -p[1]))  # x 升序，y 降序
        ans = 0
        for i, (_, y1) in enumerate(points):
            max_y = -inf
            for (_, y2) in points[i + 1:]:
                if y1 >= y2 > max_y:
                    max_y = y2
                    ans += 1
                if max_y == y1:  # 优化
                    break
        return ans

###java

class Solution {
    public int numberOfPairs(int[][] points) {
        // x 升序，y 降序
        Arrays.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            int y1 = points[i][1];
            int maxY = Integer.MIN_VALUE;
            for (int j = i + 1; j < points.length && maxY < y1; j++) {
                int y2 = points[j][1];
                if (y2 <= y1 && y2 > maxY) {
                    maxY = y2;
                    ans++;
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        // x 升序，y 降序
        ranges::sort(points, {}, [](auto& p) { return pair(p[0], -p[1]); });
        int ans = 0, n = points.size();
        for (int i = 0; i < n; i++) {
            int y1 = points[i][1];
            int max_y = INT_MIN;
            for (int j = i + 1; j < n && max_y < y1; j++) {
                int y2 = points[j][1];
                if (y2 <= y1 && y2 > max_y) {
                    max_y = y2;
                    ans++;
                }
            }
        }
        return ans;
    }
};

###c

int cmp(const void* p, const void* q) {
    int* a = *(int**)p;
    int* b = *(int**)q;
    // x 升序，y 降序
    return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
}

int numberOfPairs(int** points, int pointsSize, int* pointsColSize) {
    qsort(points, pointsSize, sizeof(int*), cmp);
    int ans = 0;
    for (int i = 0; i < pointsSize; i++) {
        int y1 = points[i][1];
        int max_y = INT_MIN;
        for (int j = i + 1; j < pointsSize && max_y < y1; j++) {
            int y2 = points[j][1];
            if (y2 <= y1 && y2 > max_y) {
                max_y = y2;
                ans++;
            }
        }
    }
    return ans;
}

###go

func numberOfPairs(points [][]int) (ans int) {
// x 升序，y 降序
slices.SortFunc(points, func(a, b []int) int { return cmp.Or(a[0]-b[0], b[1]-a[1]) })
for i, p := range points {
y1 := p[1]
maxY := math.MinInt
for _, q := range points[i+1:] {
y2 := q[1]
if y2 <= y1 && y2 > maxY {
maxY = y2
ans++
}
if maxY == y1 { // 优化
break
}
}
}
return
}

###js

var numberOfPairs = function(points) {
    points.sort((a, b) => a[0] - b[0] || b[1] - a[1]); // x 升序，y 降序
    const n = points.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const y1 = points[i][1];
        let max_y = -Infinity;
        for (let j = i + 1; j < n && max_y < y1; j++) {
            const y2 = points[j][1];
            if (y2 <= y1 && y2 > max_y) {
                max_y = y2;
                ans++;
            }
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn number_of_pairs(mut points: Vec<Vec<i32>>) -> i32 {
        points.sort_unstable_by_key(|p| (p[0], -p[1])); // x 升序，y 降序
        let mut ans = 0;
        for (i, p) in points.iter().enumerate() {
            let y1 = p[1];
            let mut max_y = i32::MIN;
            for q in &points[i + 1..] {
                let y2 = q[1];
                if y2 <= y1 && y2 > max_y {
                    max_y = y2;
                    ans += 1;
                }
                if max_y == y1 { // 优化
                    break;
                }
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 为 $\textit{points}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。Python 可以用循环代替切片。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

O(n^2) 做法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2024年2月4日 09:26

本题和 3027. 人员站位的方案数 II 是一样的，请看我的题解。

转化成 n 个单调递减序列，从中选最大的 k 个数（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年8月16日 09:35

平均通过率等于所有班级的通过率之和除以班级数目。由于班级数目是固定的，所以目标是最大化所有班级的通过率之和。

比如一个班级原来的通过率是 $\dfrac{1}{2}$（未约分）。

增加一个聪明学生后，通过率为 $\dfrac{1+1}{2+1}=\dfrac{2}{3}$。通过率增加了 $\dfrac{2}{3} - \dfrac{1}{2} = \dfrac{1}{6}$。
再增加一个聪明学生，通过率为 $\dfrac{2+1}{3+1}=\dfrac{3}{4}$。通过率增加了 $\dfrac{3}{4} - \dfrac{2}{3} = \dfrac{1}{12}$。

一般地，随着增加的学生越来越多，通过率的增量是递减（非递增）的。

注：用数学语言描述，函数 $f(x) = \dfrac{x+1}{x+2}$ 在 $(0,\infty)$ 上的二阶导小于 $0$。更一般地，当 $0 < a < b$ 时，函数 $f(x) = \dfrac{x+a}{x+b}$ 在 $(0,\infty)$ 上的二阶导小于 $0$。如果 $a=b$ 则 $f(x)=1$ 为常数函数。

示例 1 三个班级的初始通过率以及增加一个学生后的通过率增量如下表。比如 $3$ 这一列指的是当增加的学生从 $2$ 变成 $3$ 时，通过率的增量。注意是从 $2$ 变成 $3$，不是从 $0$ 变成 $3$。

	$0$	$1$	$2$	$3$	$4$	$\cdots$
一班	$\dfrac{1}{2}$	$\dfrac{1}{6}$	$\dfrac{1}{12}$	$\dfrac{1}{20}$	$\dfrac{1}{30}$	$\cdots$
二班	$\dfrac{3}{5}$	$\dfrac{1}{15}$	$\dfrac{1}{21}$	$\dfrac{1}{28}$	$\dfrac{1}{36}$	$\cdots$
三班	$\dfrac{2}{2}$	$0$	$0$	$0$	$0$	$\cdots$

每一行都是一个递减（非递增）的序列。

所有班级的通过率之和的最大值，相当于：

给你 $n$ 个递减（非递增）序列，第一项必选（初始通过率），然后再从剩余元素中选出最大的 $\textit{extraStudents}$ 个数（增量），计算这 $n + \textit{extraStudents}$ 数的元素和。

注：由于序列是递减的，所选元素是序列的前缀。

做法类似 23. 合并 K 个升序链表：

创建一个最大堆，堆中保存各个班级的下一个增量以及当前通过率（分子和分母）。
谁的下一个增量最大，谁就在堆顶。
循环 $\textit{extraStudents}$ 次。每次把堆顶弹出，分子分母各增加一，计算下一个增量，再重新入堆。

具体来说，如果一个班级的当前通过率为 $\dfrac{a}{b}$（未约分），那么其下一个增量为

$$
\dfrac{a+1}{b+1} - \dfrac{a}{b} = \dfrac{b-a}{b(b+1)}
$$

上式最大的班级在堆顶。

写法一：使用浮点数

###py

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        # 默认是小根堆，把增量取相反数，变成大根堆
        h = [((a - b) / (b * (b + 1)), a, b) for a, b in classes]
        heapify(h)  # 堆化，只需 O(n) 时间

        for _ in range(extraStudents):
            _, a, b = h[0]
            a += 1
            b += 1
            heapreplace(h, ((a - b) / (b * (b + 1)), a, b))  # 这样写比 pop 再 push 更快

        return sum(a / b for _, a, b in h) / len(h)

###java

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        record Node(double gain, int a, int b) {}
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Double.compare(b.gain, a.gain));

        for (int[] c : classes) {
            int a = c[0];
            int b = c[1];
            double gain = 1.0 * (b - a) / (1L * b * (b + 1));
            pq.add(new Node(gain, a, b));
        }

        while (extraStudents-- > 0) {
            Node top = pq.poll();
            int a = top.a + 1;
            int b = top.b + 1;
            double gain = 1.0 * (b - a) / (1L * b * (b + 1));
            pq.add(new Node(gain, a, b));
        }

        double sum = 0;
        int n = pq.size();
        while (!pq.isEmpty()) {
            Node top = pq.poll();
            sum += 1.0 * top.a / top.b;
        }
        return sum / n;
    }
}

###cpp

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        using DII = tuple<double, int, int>;
        auto cmp = [](const DII& a, const DII& b) {
            return get<0>(a) > get<0>(b);
        };
        priority_queue<DII, vector<DII>, decltype(cmp)> pq;

        for (auto& c : classes) {
            int a = c[0], b = c[1];
            pq.emplace(1.0 * (a - b) / (1LL * b * (b + 1)), a, b);
        }

        while (extraStudents--) {
            auto [_, a, b] = pq.top();
            pq.pop();
            a++;
            b++;
            pq.emplace(1.0 * (a - b) / (1LL * b * (b + 1)), a, b);
        }

        double sum = 0;
        int n = pq.size();
        while (!pq.empty()) {
            auto [_, a, b] = pq.top();
            pq.pop();
            sum += 1.0 * a / b;
        }
        return sum / n;
    }
};

###cpp

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        using DII = tuple<double, int, int>;
        auto cmp = [](const DII& a, const DII& b) {
            return get<0>(a) > get<0>(b);
        };

        vector<DII> h;
        for (auto& c : classes) {
            int a = c[0], b = c[1];
            h.emplace_back(1.0 * (a - b) / (1LL * b * (b + 1)), a, b);
        }
        ranges::make_heap(h, cmp); // 堆化，只需 O(n)

        while (extraStudents--) {
            ranges::pop_heap(h, cmp); // 把堆顶移到末尾
            auto& [r, a, b] = h.back();
            a++;
            b++;
            r = 1.0 * (a - b) / (1LL * b * (b + 1));
            ranges::push_heap(h, cmp); // 重新入堆
        }

        double sum = 0;
        for (auto& [_, a, b] : h) {
            sum += 1.0 * a / b;
        }
        return sum / h.size();
    }
};

###go

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
n := len(classes)
h := make(hp, n)
for i, c := range classes {
a, b := c[0], c[1]
h[i] = tuple{float64(b-a) / float64(b*(b+1)), a, b}
}
heap.Init(&h) // 堆化，只需 O(n) 时间

for range extraStudents {
h[0].a++
h[0].b++
a, b := h[0].a, h[0].b
h[0].gain = float64(b-a) / float64(b*(b+1))
heap.Fix(&h, 0)
}

sum := 0.0
for _, t := range h {
sum += float64(t.a) / float64(t.b)
}
return sum / float64(n)
}

type tuple struct {
gain float64
a, b int
}
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].gain > h[j].gain }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (hp) Push(any)             {} // 没用到，可以不实现
func (hp) Pop() (_ any)         { return }

写法二：不使用浮点数

浮点数有舍入误差，计算结果不一定准确。两个分数比大小，可以把 $\dfrac{a}{b} > \dfrac{c}{d}$ 改成等价的 $ad > bc$，从而不使用浮点数。

###py

class Pair:
    __slots__ = 'a', 'b'

    def __init__(self, a: int, b: int):
        self.a = a
        self.b = b

    def __lt__(self, other: 'Pair') -> bool:
        return (self.b - self.a) * other.b * (other.b + 1) > (other.b - other.a) * self.b * (self.b + 1)


class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        h = [Pair(a, b) for a, b in classes]
        heapify(h)

        for _ in range(extraStudents):
            p = h[0]
            heapreplace(h, Pair(p.a + 1, p.b + 1))

        return sum(p.a / p.b for p in h) / len(h)

###java

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
            Long.compare(1L * (b[1] - b[0]) * a[1] * (a[1] + 1), 1L * (a[1] - a[0]) * b[1] * (b[1] + 1))
        );

        for (int[] c : classes) {
            pq.add(c);
        }

        while (extraStudents-- > 0) {
            int[] top = pq.poll();
            top[0]++;
            top[1]++;
            pq.add(top);
        }

        double sum = 0;
        int n = pq.size();
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            sum += 1.0 * top[0] / top[1];
        }
        return sum / n;
    }
}

###cpp

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        struct Pair { int a, b; };
        auto cmp = [](const Pair& a, const Pair& b) {
            return 1LL * (a.b - a.a) * b.b * (b.b + 1) < 1LL * (b.b - b.a) * a.b * (a.b + 1);
        };
        priority_queue<Pair, vector<Pair>, decltype(cmp)> pq;

        for (auto& c : classes) {
            pq.emplace(c[0], c[1]);
        }

        while (extraStudents--) {
            auto [a, b] = pq.top();
            pq.pop();
            pq.emplace(a + 1, b + 1);
        }

        double sum = 0;
        int n = pq.size();
        while (!pq.empty()) {
            auto [a, b] = pq.top();
            pq.pop();
            sum += 1.0 * a / b;
        }
        return sum / n;
    }
};

###cpp

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        struct Pair { int a, b; };
        auto cmp = [](const Pair& a, const Pair& b) {
            return 1LL * (a.b - a.a) * b.b * (b.b + 1) < 1LL * (b.b - b.a) * a.b * (a.b + 1);
        };

        vector<Pair> h;
        for (auto& c : classes) {
            h.emplace_back(c[0], c[1]);
        }
        ranges::make_heap(h, cmp); // 堆化，只需 O(n)

        while (extraStudents--) {
            ranges::pop_heap(h, cmp); // 把堆顶移到末尾
            auto& [a, b] = h.back();
            a++;
            b++;
            ranges::push_heap(h, cmp); // 重新入堆
        }

        double sum = 0;
        for (auto& [a, b] : h) {
            sum += 1.0 * a / b;
        }
        return sum / h.size();
    }
};

###go

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
n := len(classes)
h := make(hp, n)
for i, c := range classes {
h[i] = pair{c[0], c[1]}
}
heap.Init(&h)

for range extraStudents {
h[0].a++
h[0].b++
heap.Fix(&h, 0)
}

sum := 0.0
for _, t := range h {
sum += float64(t.a) / float64(t.b)
}
return sum / float64(n)
}

type pair struct{ a, b int }
type hp []pair

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return (a.b-a.a)*b.b*(b.b+1) > (b.b-b.a)*a.b*(a.b+1)
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (hp) Push(any)        {}
func (hp) Pop() (_ any)    { return }

复杂度分析

时间复杂度：$\mathcal{O}(n + \textit{extraStudents}\cdot\log n)$ 或 $\mathcal{O}((n + \textit{extraStudents})\cdot\log n)$，其中 $n$ 是 $\textit{classes}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面数据结构题单的「五、堆（优先队列）」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

数独怎么玩，题目就怎么做：回溯+堆优化（Python/Java/C++/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年8月30日 11:24

前置题目

36. 有效的数独。学会如何把当前位置转化成「宫」的位置。
46. 全排列。视频讲解：排列型回溯【基础算法精讲 16】。

核心思路

游玩数独的技巧之一是，优先填待定数字最少的空格子。

示例 1 如上图。看正中间的空格子 $\textit{board}[4][4]$：

横着看，这一行有 $1,3,4,8$。
竖着看，这一列有 $1,2,6,7,8,9$。
正中间的宫有 $2,3,6,8$。
所以我们能填的数字只有 $5$。

填完 $\textit{board}[4][4]=5$ 后，继续找下一个待定数字最少的空格子。重复上述过程，直到所有格子都填完。

如果一个格子有多个数字可以填，那么就像 46. 全排列那样，枚举填入的数字。

注：题目保证输入的数独有唯一解。

实现细节

类似 36. 有效的数独，用三组哈希表（布尔数组）维护：

$\textit{rowSet}[i]$ 维护第 $i$ 行填入的数字。
$\textit{colSet}[j]$ 维护第 $j$ 列填入的数字。
$\textit{subBoxSet}[i'][j']$ 维护 $(i',j')$ 宫填入的数字。其中 $\textit{board}[i][j]$ 在 $\left(\left\lfloor\dfrac{i}{3}\right\rfloor, \left\lfloor\dfrac{j}{3}\right\rfloor \right)$ 这个宫。

为了快速找到待定数字最少的空格子，用一个最小堆维护三元组 $(\textit{candidates},i,j)$，其中 $\textit{candidates}$ 等于 $(i,j)$ 这个空格子可以填入的数字个数。那么堆顶就是 $\textit{candidates}$ 最少的空格子。

然而，当我们把数字填入一个空格子时，同一行、同一列、同一宫的其余空格子的 $\textit{candidates}$ 都会减少 $1$。难道要动态修改堆中元素？

我们采取一个简单的折中方案：在枚举填入数字的循环中，重新统计当前格子 $(i,j)$ 的实际待定数字个数 $\textit{candidates}'$。在恢复现场的时候，把三元组 $(\textit{candidates}',i,j)$ 入堆。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        row_set = [set() for _ in range(9)]  # 每行填入的数字
        col_set = [set() for _ in range(9)]  # 每列填入的数字
        sub_box_set = [[set() for _ in range(3)] for _ in range(3)]  # 每宫填入的数字
        empty_pos = []  # 空格子的位置

        for i, row in enumerate(board):
            for j, b in enumerate(row):
                if b == '.':
                    empty_pos.append((i, j))  # 记录空格子的位置
                else:
                    x = int(b)
                    # 标记行、列、宫包含数字 x
                    row_set[i].add(x)
                    col_set[j].add(x)
                    sub_box_set[i // 3][j // 3].add(x)

        # get_candidates(i, j) 计算 (i, j) 这个空格子的待定数字个数，最小的在堆顶
        get_candidates = lambda i, j: 9 - len(row_set[i] | col_set[j] | sub_box_set[i // 3][j // 3])
        empty_heap = [(get_candidates(i, j), i, j) for i, j in empty_pos]
        heapify(empty_heap)

        # 每次递归，选一个空格子，枚举填入的数字
        def dfs() -> bool:
            if not empty_heap:  # 所有格子都已填入数字
                return True  # 完成数独

            # 数独玩法：优先考虑待定数字个数最少的空格子
            _, i, j = heappop(empty_heap)

            candidates = 0  # 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
            # 枚举 1~9 中没填过的数字 x，填入 board[i][j]
            for x in range(1, 10):
                if x in row_set[i] or x in col_set[j] or x in sub_box_set[i // 3][j // 3]:
                    continue  # x 填过了

                # 把数字 x 转成字符，填入 board[i][j]
                board[i][j] = digits[x]
                # 标记行、列、宫包含数字 x
                row_set[i].add(x)
                col_set[j].add(x)
                sub_box_set[i // 3][j // 3].add(x)

                # 填下一个空格子
                if dfs():
                    return True  # 完成数独

                # 恢复现场（撤销）
                # 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
                row_set[i].remove(x)
                col_set[j].remove(x)
                sub_box_set[i // 3][j // 3].remove(x)

                # 统计待定数字个数
                candidates += 1

            # 恢复现场（撤销）
            heappush(empty_heap, (candidates, i, j))  # 重新入堆（更新待定数字个数）
            # 所有填法都不行，说明之前（祖先节点）的填法是错的
            return False

        dfs()

class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] rowHas = new boolean[9][9]; // rowHas[i][x] 表示 i 行是否有数字 x
        boolean[][] colHas = new boolean[9][9]; // colHas[j][x] 表示 j 列是否有数字 x
        boolean[][][] subBoxHas = new boolean[3][3][9]; // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x
        List<int[]> emptyPos = new ArrayList<>(); // 空格子的位置

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    emptyPos.add(new int[]{i, j}); // 记录空格子的位置
                } else {
                    int x = board[i][j] - '1'; // 字符 '1'~'9' 转成数字 0~8
                    // 标记行、列、宫包含数字 x
                    rowHas[i][x] = colHas[j][x] = subBoxHas[i / 3][j / 3][x] = true;
                }
            }
        }

        PriorityQueue<int[]> emptyPQ = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int[] pos : emptyPos) {
            int i = pos[0];
            int j = pos[1];
            int candidates = getCandidates(i, j, rowHas, colHas, subBoxHas);
            emptyPQ.offer(new int[]{candidates, i, j}); // 待定数字个数最少的在堆顶
        }

        dfs(board, rowHas, colHas, subBoxHas, emptyPQ);
    }

    // 计算 (i, j) 这个空格子的待定数字个数
    private int getCandidates(int i, int j, boolean[][] rowHas, boolean[][] colHas, boolean[][][] subBoxHas) {
        int candidates = 9;
        for (int x = 0; x < 9; x++) {
            if (rowHas[i][x] || colHas[j][x] || subBoxHas[i / 3][j / 3][x]) {
                candidates--;
            }
        }
        return candidates;
    }

    // 每次递归，选一个空格子，枚举填入的数字
    private boolean dfs(char[][] board, boolean[][] rowHas, boolean[][] colHas, boolean[][][] subBoxHas, PriorityQueue<int[]> emptyPQ) {
        if (emptyPQ.isEmpty()) { // 所有格子都已填入数字
            return true; // 完成数独
        }

        // 数独玩法：优先考虑待定数字个数最少的空格子
        int[] top = emptyPQ.poll();
        int i = top[1];
        int j = top[2];

        int candidates = 0; // 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
        // 枚举没填过的数字 x，填入 board[i][j]
        for (int x = 0; x < 9; x++) {
            if (rowHas[i][x] || colHas[j][x] || subBoxHas[i / 3][j / 3][x]) {
                continue; // x 填过了
            }

            // 填入 board[i][j]
            board[i][j] = (char) ('1' + x);
            // 标记行、列、宫包含数字 x
            rowHas[i][x] = colHas[j][x] = subBoxHas[i / 3][j / 3][x] = true;

            // 填下一个空格子
            if (dfs(board, rowHas, colHas, subBoxHas, emptyPQ)) {
                return true; // 完成数独
            }

            // 恢复现场（撤销）
            // 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
            rowHas[i][x] = colHas[j][x] = subBoxHas[i / 3][j / 3][x] = false;

            // 统计待定数字个数
            candidates++;
        }

        // 恢复现场（撤销）
        emptyPQ.offer(new int[]{candidates, i, j}); // 重新入堆（更新待定数字个数）
        // 所有填法都不行，说明之前（祖先节点）的填法是错的
        return false;
    }
}

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        bool row_has[9][9]{}; // row_has[i][x] 表示 i 行是否有数字 x
        bool col_has[9][9]{}; // col_has[j][x] 表示 j 列是否有数字 x
        bool sub_box_has[3][3][9]{}; // sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x
        vector<pair<int, int>> empty_pos; // 空格子的位置

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char b = board[i][j];
                if (b == '.') {
                    empty_pos.emplace_back(i, j); // 记录空格子的位置
                } else {
                    int x = b - '1'; // 字符 '1'~'9' 转成数字 0~8
                    // 标记行、列、宫包含数字 x
                    row_has[i][x] = col_has[j][x] = sub_box_has[i / 3][j / 3][x] = true;
                }
            }
        }

        // 计算 (i, j) 这个空格子的待定数字个数
        auto get_candidates = [&](int i, int j) -> int {
            int candidates = 9;
            for (int x = 0; x < 9; x++) {
                if (row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x]) {
                    candidates--;
                }
            }
            return candidates;
        };

        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> empty_pq;
        for (auto& [i, j] : empty_pos) {
            empty_pq.emplace(get_candidates(i, j), i, j);
        }

        // 每次递归，选一个空格子，枚举填入的数字
        // lambda 递归
        auto dfs = [&](this auto&& dfs) -> bool {
            if (empty_pq.empty()) { // 所有格子都已填入数字
                return true; // 完成数独
            }

            // 数独玩法：优先考虑待定数字个数最少的空格子
            auto [_, i, j] = empty_pq.top();
            empty_pq.pop();

            int candidates = 0; // 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
            // 枚举没填过的数字 x，填入 board[i][j]
            for (int x = 0; x < 9; x++) {
                if (row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x]) {
                    continue; // x 填过了
                }

                // 填入 board[i][j]
                board[i][j] = '1' + x;
                // 标记行、列、宫包含数字 x
                row_has[i][x] = col_has[j][x] = sub_box_has[i / 3][j / 3][x] = true;

                // 填下一个空格子
                if (dfs()) {
                    return true; // 完成数独
                }

                // 恢复现场（撤销）
                // 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
                row_has[i][x] = col_has[j][x] = sub_box_has[i / 3][j / 3][x] = false;

                // 统计待定数字个数
                candidates++;
            }

            // 恢复现场（撤销）
            empty_pq.emplace(candidates, i, j); // 重新入堆（更新待定数字个数）
            // 所有填法都不行，说明之前（祖先节点）的填法是错的
            return false;
        };

        dfs();
    }
};

func solveSudoku(board [][]byte) {
    rowHas := [9][9]bool{}       // rowHas[i][x] 表示 i 行是否有数字 x
    colHas := [9][9]bool{}       // colHas[j][x] 表示 j 列是否有数字 x
    subBoxHas := [3][3][9]bool{} // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x
    emptyPos := [][2]int{}       // 空格子的位置

    for i, row := range board {
        for j, b := range row {
            if b == '.' {
                emptyPos = append(emptyPos, [2]int{i, j}) // 记录空格子的位置
            } else {
                x := b - '1' // 字符 '1'~'9' 转成数字 0~8
                // 标记行、列、宫包含数字 x
                rowHas[i][x] = true
                colHas[j][x] = true
                subBoxHas[i/3][j/3][x] = true
            }
        }
    }

    // 计算 (i, j) 这个空格子的待定数字个数
    getCandidates := func(i, j int) int {
        candidates := 9
        for x := range 9 {
            if rowHas[i][x] || colHas[j][x] || subBoxHas[i/3][j/3][x] {
                candidates--
            }
        }
        return candidates
    }

    emptyHeap := &hp{}
    for _, pos := range emptyPos {
        i, j := pos[0], pos[1]
        heap.Push(emptyHeap, tuple{getCandidates(i, j), i, j})
    }
    heap.Init(emptyHeap)

    // 每次递归，选一个空格子，枚举填入的数字
    var dfs func() bool
    dfs = func() bool {
        if emptyHeap.Len() == 0 { // 所有格子都已填入数字
            return true // 完成数独
        }

        // 数独玩法：优先考虑待定数字个数最少的空格子
        t := heap.Pop(emptyHeap).(tuple)
        i, j := t.i, t.j

        candidates := 0 // 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
        // 枚举没填过的数字 x，填入 board[i][j]
        for x := range 9 {
            if rowHas[i][x] || colHas[j][x] || subBoxHas[i/3][j/3][x] {
                continue // x 填过了
            }

            // 填入 board[i][j]
            board[i][j] = '1' + byte(x)
            // 标记行、列、宫包含数字 x
            rowHas[i][x] = true
            colHas[j][x] = true
            subBoxHas[i/3][j/3][x] = true

            // 填下一个空格子
            if dfs() {
                return true // 完成数独
            }

            // 恢复现场（撤销）
            // 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
            rowHas[i][x] = false
            colHas[j][x] = false
            subBoxHas[i/3][j/3][x] = false

            // 统计待定数字个数
            candidates++
        }

        // 恢复现场（撤销）
        heap.Push(emptyHeap, tuple{candidates, i, j}) // 重新入堆（更新待定数字个数）
        // 所有填法都不行，说明之前（祖先节点）的填法是错的
        return false
    }

    dfs()
}

type tuple struct{ candidates, i, j int }
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].candidates < h[j].candidates }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

var solveSudoku = function(board) {
    const rowHas = Array.from({length: 9}, () => Array(9).fill(false)); // rowHas[i][x] 表示 i 行是否有数字 x
    const colHas = Array.from({length: 9}, () => Array(9).fill(false)); // colHas[j][x] 表示 j 列是否有数字 x
    const subBoxHas = Array.from({length: 3}, () => Array.from({length: 3}, () => Array(9).fill(false))); // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x
    const emptyPos = []; // 空格子的位置

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const b = board[i][j];
            if (b === '.') {
                emptyPos.push([i, j]); // 记录空格子的位置
            } else {
                const x = b.charCodeAt(0) - '1'.charCodeAt(0); // 字符 '1'~'9' 转成数字 0~8
                // 标记行、列、宫包含数字 x
                rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x] = true;
            }
        }
    }

    // 计算 (i, j) 这个空格子的待定数字个数
    function getCandidates(i, j) {
        let candidates = 9;
        for (let x = 0; x < 9; x++) {
            if (rowHas[i][x] || colHas[j][x] || subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x]) {
                candidates--;
            }
        }
        return candidates;
    }

    const emptyPQ = new MinPriorityQueue(e => e[0]);
    for (const [i, j] of emptyPos) {
        emptyPQ.enqueue([getCandidates(i, j), i, j]);
    }

    // 每次递归，选一个空格子，枚举填入的数字
    function dfs() {
        if (emptyPQ.isEmpty()) { // 所有格子都已填入数字
            return true; // 完成数独
        }

        // 数独玩法：优先考虑待定数字个数最少的空格子
        const [_, i, j] = emptyPQ.dequeue();

        let candidates = 0; // 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
        // 枚举没填过的数字 x，填入 board[i][j]
        for (let x = 0; x < 9; x++) {
            if (rowHas[i][x] || colHas[j][x] || subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x]) {
                continue; // x 填过了
            }

            // 填入 board[i][j]
            board[i][j] = (x + 1).toString(); 
            // 标记行、列、宫包含数字 x
            rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x] = true;

            // 填下一个空格子
            if (dfs()) {
                return true; // 完成数独
            }

            // 恢复现场（撤销）
            // 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
            rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x] = false;

            // 统计待定数字个数
            candidates++;
        }

        // 恢复现场（撤销）
        emptyPQ.enqueue([candidates, i, j]); // 重新入堆（更新待定数字个数）
        // 所有填法都不行，说明之前（祖先节点）的填法是错的
        return false;
    }

    dfs();
};

use std::collections::BinaryHeap;

impl Solution {
    pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
        let mut row_has = [[false; 9]; 9]; // row_has[i][x] 表示 i 行是否有数字 x
        let mut col_has = [[false; 9]; 9]; // col_has[j][x] 表示 j 列是否有数字 x
        let mut sub_box_has = [[[false; 9]; 3]; 3]; // sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x
        let mut empty_pos = vec![]; // 空格子的位置

        for (i, row) in board.iter().enumerate() {
            for (j, &b) in row.iter().enumerate() {
                if b == '.' {
                    empty_pos.push((i, j)); // 记录空格子的位置
                } else {
                    let x = (b as u8 - b'1') as usize; // 字符 '1'~'9' 转成数字 0~8
                    // 标记行、列、宫包含数字 x
                    row_has[i][x] = true;
                    col_has[j][x] = true;
                    sub_box_has[i / 3][j / 3][x] = true;
                }
            }
        }

        // 计算 (i, j) 这个空格子的待定数字个数
        let get_candidates = |i: usize, j: usize| -> i8 {
            let mut candidates = 9;
            for x in 0..9 {
                if row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x] {
                    candidates -= 1;
                }
            }
            candidates
        };

        let mut empty_heap = BinaryHeap::new();
        for (i, j) in empty_pos {
            // 取相反数，把 empty_pq 当作最小堆
            empty_heap.push((-get_candidates(i, j), i, j));
        }

        // 每次递归，选一个空格子，枚举填入的数字
        fn dfs(board: &mut [Vec<char>], row_has: &mut [[bool; 9]; 9], col_has: &mut [[bool; 9]; 9], sub_box_has: &mut [[[bool; 9]; 3]; 3], empty_heap: &mut BinaryHeap<(i8, usize, usize)>) -> bool {
            if empty_heap.is_empty() { // 所有格子都已填入数字
                return true; // 完成数独
            }

            // 数独玩法：优先考虑待定数字个数最少的空格子
            let (_, i, j) = empty_heap.pop().unwrap();

            let mut candidates = 0; // 受之前填入的数字影响，实际待定数字个数可能比入堆时的少，需要重新计算
            // 枚举没填过的数字 x，填入 board[i][j]
            for x in 0..9 {
                if row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x] {
                    continue; // x 填过了
                }

                // 填入 board[i][j]
                board[i][j] = (b'1' + x as u8) as char;
                // 标记行、列、宫包含数字 x
                row_has[i][x] = true;
                col_has[j][x] = true;
                sub_box_has[i / 3][j / 3][x] = true;

                // 填下一个空格子
                if dfs(board, row_has, col_has, sub_box_has, empty_heap) {
                    return true; // 完成数独
                }

                // 恢复现场（撤销）
                // 注意 board[i][j] 无需恢复现场，因为我们会直接覆盖掉之前填入的数字
                row_has[i][x] = false;
                col_has[j][x] = false;
                sub_box_has[i / 3][j / 3][x] = false;

                // 统计待定数字个数
                candidates += 1;
            }

            // 恢复现场（撤销）
            empty_heap.push((-candidates, i, j)); // 重新入堆（更新待定数字个数）
            // 所有填法都不行，说明之前（祖先节点）的填法是错的
            false
        }

        dfs(board, &mut row_has, &mut col_has, &mut sub_box_has, &mut empty_heap);
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(9^m\log m)$，其中 $m\le 81$ 是空格的个数。搜索树的高度为 $m$，每个节点至多有 $9$ 个儿子，所以搜索树有 $\mathcal{O}(9^m)$ 个节点。每个节点需要 $\mathcal{O}(\log m)$ 的实际操作堆。注意这只是一个上界，实际复杂度远小于上界。
空间复杂度：$\mathcal{O}(m)$。

注：还有一些更高级的算法，如 Dancing Links。

专题训练

见下面回溯题单的「§4.5 排列型回溯」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

记录每行每列每宫中的数字是否出现（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年8月30日 08:04

我们需要满足三个规则：

每行不能有相同数字。
每列不能有相同数字。
每宫不能有相同数字。注：宫是大小为 $3\times 3$ 的子矩阵。

对于宫，我们可以把 $\textit{board}$ 视作 $3\times 3$ 个大小为 $3\times 3$ 的子矩阵。其中 $\textit{board}[i][j]$ 在 $\left(\left\lfloor\dfrac{i}{3}\right\rfloor, \left\lfloor\dfrac{j}{3}\right\rfloor \right)$ 这个宫。例如右下角 $\textit{board}[8][8]$ 在 $\left(\left\lfloor\dfrac{8}{3}\right\rfloor, \left\lfloor\dfrac{8}{3}\right\rfloor \right) = (2,2)$ 这个宫，即右下的 $3\times 3$ 子矩阵。

判断是否满足规则：

对于每行，在遍历的同时，用二维布尔数组 $\textit{rowHas}$ 标记遍历过的数字，其中 $\textit{rowHas}[i][x] = \texttt{true}$ 表示第 $i$ 行有数字 $x$。比如之前遍历到数字 $6$，标记 $\textit{rowHas}[i][6] = \texttt{true}$；然后又遍历到数字 $6$，发现 $\textit{rowHas}[i][6] = \texttt{true}$，则说明有两个 $6$，数独不是有效的，返回 $\texttt{false}$。
对于每列，在遍历的同时，用二维布尔数组 $\textit{colHas}$ 标记遍历过的数字，其中 $\textit{colHas}[j][x] = \texttt{true}$ 表示第 $j$ 列有数字 $x$。如果继续遍历，遍历到相同数字，即发现 $\textit{colHas}[j][x] = \texttt{true}$，那么数独不是有效的，返回 $\texttt{false}$。
对于每宫，在遍历的同时，用三维布尔数组 $\textit{subBoxHas}$ 标记遍历过的数字。设 $i' = \left\lfloor\dfrac{i}{3}\right\rfloor$，$j' = \left\lfloor\dfrac{j}{3}\right\rfloor$，定义 $\textit{subBoxHas}[i'][j'][x] = \texttt{true}$ 表示 $(i',j')$ 宫有数字 $x$。如果继续遍历，遍历到相同数字，即发现 $\textit{subBoxHas}[i'][j'][x] = \texttt{true}$，那么数独不是有效的，返回 $\texttt{false}$。

如果遍历过程中没有返回 $\texttt{false}$，那么数独是有效的，最终返回 $\texttt{true}$。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_has = [[False] * 9 for _ in range(9)]  # row_has[i][x] 表示 i 行是否有数字 x
        col_has = [[False] * 9 for _ in range(9)]  # col_has[j][x] 表示 j 列是否有数字 x
        sub_box_has = [[[False] * 9 for _ in range(3)] for _ in range(3)]  # sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x

        for i, row in enumerate(board):
            for j, b in enumerate(row):
                if b == '.':
                    continue
                x = int(b) - 1  # 字符 '1'~'9' 转成数字 0~8
                if row_has[i][x] or col_has[j][x] or sub_box_has[i // 3][j // 3][x]:  # 重复遇到数字 x
                    return False
                # 标记行、列、宫包含数字 x
                row_has[i][x] = col_has[j][x] = sub_box_has[i // 3][j // 3][x] = True

        return True

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_has = set()  # (i, x)
        col_has = set()  # (j, x)
        sub_box_has = set()  # (i // 3, j // 3, x)

        for i, row in enumerate(board):
            for j, x in enumerate(row):
                if x == '.':
                    continue
                if (i, x) in row_has or (j, x) in col_has or (i // 3, j // 3, x) in sub_box_has:  # 重复遇到数字 x
                    return False
                # 标记行、列、宫包含数字 x
                row_has.add((i, x))
                col_has.add((j, x))
                sub_box_has.add((i // 3, j // 3, x))

        return True

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rowHas = new boolean[9][9]; // rowHas[i][x] 表示 i 行是否有数字 x
        boolean[][] colHas = new boolean[9][9]; // colHas[j][x] 表示 j 列是否有数字 x
        boolean[][][] subBoxHas = new boolean[3][3][9]; // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char b = board[i][j];
                if (b == '.') {
                    continue;
                }
                int x = b - '1'; // 字符 '1'~'9' 转成数字 0~8
                if (rowHas[i][x] || colHas[j][x] || subBoxHas[i / 3][j / 3][x]) { // 重复遇到数字 x
                    return false;
                }
                // 标记行、列、宫包含数字 x
                rowHas[i][x] = colHas[j][x] = subBoxHas[i / 3][j / 3][x] = true;
            }
        }

        return true;
    }
}

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row_has[9][9]{}; // row_has[i][x] 表示 i 行是否有数字 x
        bool col_has[9][9]{}; // col_has[j][x] 表示 j 列是否有数字 x
        bool sub_box_has[3][3][9]{}; // sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char b = board[i][j];
                if (b == '.') {
                    continue;
                }
                int x = b - '1'; // 字符 '1'~'9' 转成数字 0~8
                if (row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x]) { // 重复遇到数字 x
                    return false;
                }
                // 标记行、列、宫包含数字 x
                row_has[i][x] = col_has[j][x] = sub_box_has[i / 3][j / 3][x] = true;
            }
        }

        return true;
    }
};

bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    bool row_has[9][9] = {}; // row_has[i][x] 表示 i 行是否有数字 x
    bool col_has[9][9] = {}; // col_has[j][x] 表示 j 列是否有数字 x
    bool sub_box_has[3][3][9] = {}; // sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char b = board[i][j];
            if (b == '.') {
                continue;
            }
            int x = b - '1'; // 字符 '1'~'9' 转成数字 0~8
            if (row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x]) { // 重复遇到数字 x
                return false;
            }
            // 标记行、列、宫包含数字 x
            row_has[i][x] = col_has[j][x] = sub_box_has[i / 3][j / 3][x] = true;
        }
    }

    return true;
}

func isValidSudoku(board [][]byte) bool {
    rowHas := [9][9]bool{} // rowHas[i][x] 表示 i 行是否有数字 x
    colHas := [9][9]bool{} // colHas[j][x] 表示 j 列是否有数字 x
    subBoxHas := [3][3][9]bool{} // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x

    for i, row := range board {
        for j, b := range row {
            if b == '.' {
                continue
            }
            x := b - '1' // 字符 '1'~'9' 转成数字 0~8
            if rowHas[i][x] || colHas[j][x] || subBoxHas[i/3][j/3][x] { // 重复遇到数字 x
                return false
            }
            // 标记行、列、宫包含数字 x
            rowHas[i][x] = true
            colHas[j][x] = true
            subBoxHas[i/3][j/3][x] = true
        }
    }

    return true
}

var isValidSudoku = function(board) {
    const rowHas = Array.from({ length: 9 }, () => Array(9).fill(false)); // rowHas[i][x] 表示 i 行是否有数字 x
    const colHas = Array.from({ length: 9 }, () => Array(9).fill(false)); // colHas[j][x] 表示 j 列是否有数字 x
    const subBoxHas = Array.from({ length: 3 }, () => Array.from({ length: 3 }, () => Array(9).fill(false))); // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const b = board[i][j];
            if (b === '.') {
                continue;
            }
            const x = b.charCodeAt(0) - '1'.charCodeAt(0); // 字符 '1'~'9' 转成数字 0~8
            if (rowHas[i][x] || colHas[j][x] || subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x]) { // 重复遇到数字 x
                return false;
            }
            // 标记行、列、宫包含数字 x
            rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i / 3)][Math.floor(j / 3)][x] = true;
        }
    }

    return true;
};

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut row_has = [[false; 9]; 9]; // row_has[i][x] 表示 i 行是否有数字 x
        let mut col_has = [[false; 9]; 9]; // col_has[j][x] 表示 j 列是否有数字 x
        let mut sub_box_has = [[[false; 9]; 3]; 3]; // sub_box_has[i'][j'][x] 表示 (i',j') 宫是否有数字 x

        for (i, row) in board.into_iter().enumerate() {
            for (j, b) in row.into_iter().enumerate() {
                if b == '.' {
                    continue;
                }
                let x = (b as u8 - b'1') as usize; // 字符 '1'~'9' 转成数字 0~8
                if row_has[i][x] || col_has[j][x] || sub_box_has[i / 3][j / 3][x] { // 重复遇到数字 x
                    return false;
                }
                // 标记行、列、宫包含数字 x
                row_has[i][x] = true;
                col_has[j][x] = true;
                sub_box_has[i / 3][j / 3][x] = true;
            }
        }

        true
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n=9$ 是 $\textit{board}$ 的长度。
空间复杂度：$\mathcal{O}(n^2)$。

思考题

如果要填充这个数独呢？

见 37. 解数独。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

O(1) 数学公式（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2024年1月28日 12:26

根据题意，每回合摘一朵花，摘到最后一朵花的人获胜。所以当且仅当鲜花个数 $x+y$ 是奇数时，Alice 摘到最后一朵花。

要让 $x+y$ 是奇数：

如果 $x$ 是偶数，那么 $y$ 必须是奇数。
如果 $x$ 是奇数，那么 $y$ 必须是偶数。

$[1,n]$ 中有 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 个偶数，$\left\lceil\dfrac{n}{2}\right\rceil$ 个奇数。$[1,m]$ 中有 $\left\lfloor\dfrac{m}{2}\right\rfloor$ 个偶数，$\left\lceil\dfrac{m}{2}\right\rceil$ 个奇数。

所以答案为

$$
\left\lfloor\dfrac{n}{2}\right\rfloor\cdot \left\lceil\dfrac{m}{2}\right\rceil + \left\lceil\dfrac{n}{2}\right\rceil\cdot \left\lfloor\dfrac{m}{2}\right\rfloor
$$

考虑化简上式：

当 $n$ 是偶数时，原式等于 $\dfrac{n}{2}\left(\left\lceil\dfrac{m}{2}\right\rceil + \left\lfloor\dfrac{m}{2}\right\rfloor\right) = \dfrac{nm}{2} = \left\lfloor\dfrac{nm}{2}\right\rfloor$。
当 $m$ 是偶数时，原式等于 $\dfrac{m}{2}\left(\left\lceil\dfrac{n}{2}\right\rceil + \left\lfloor\dfrac{n}{2}\right\rfloor\right) = \dfrac{nm}{2} = \left\lfloor\dfrac{nm}{2}\right\rfloor$。
当 $n$ 和 $m$ 都是奇数时，原式等于 $\dfrac{n-1}{2}\cdot \dfrac{m+1}{2} + \dfrac{n+1}{2}\cdot \dfrac{m-1}{2} = \dfrac{nm-1}{2} = \left\lfloor\dfrac{nm}{2}\right\rfloor$。

所以原式可化简为

$$
\left\lfloor\dfrac{nm}{2}\right\rfloor
$$

注：也可以利用国际象棋棋盘推导，见视频讲解。

###py

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return n * m // 2

###java

class Solution {
    public long flowerGame(int n, int m) {
        return (long) n * m / 2;
    }
}

###cpp

class Solution {
public:
    long long flowerGame(int n, int m) {
        return 1LL * n * m / 2;
    }
};

###c

long long flowerGame(int n, int m) {
    return 1LL * n * m / 2;
}

###go

func flowerGame(n, m int) int64 {
return int64(n) * int64(m) / 2
}

###js

var flowerGame = function(n, m) {
    return Math.floor(n * m / 2);
};

###rust

impl Solution {
    pub fn flower_game(n: i32, m: i32) -> i64 {
        n as i64 * m as i64 / 2
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

【模板】遍历对角线（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年2月9日 13:09

对于每条对角线，行号 $i$ 减列号 $j$ 是一个定值。比如正中间对角线（主对角线）的 $i-j$ 恒为 $0$。（可以回想一下 51. N 皇后的写法）

设 $k=i-j+n$，那么右上角那条对角线的 $k=0-(n-1)+n = 1$，左下角那条对角线的 $k=(m-1)-0+n = m+n-1$。（本题 $m=n$）

枚举 $k=1,2,3,\dots,m+n-1$，就相当于在从右上到左下，一条一条地枚举对角线。

由于 $i-j+n=k$，知道 $j$ 就知道 $i$，所以我们只需要计算出每条对角线的 $j$ 的最小值和最大值，就可以开始遍历对角线了。

由于 $j=i-k+n$，当 $i=0$ 时 $j$ 取到最小值 $n-k$，但这个数不能是负数，所以最小的 $j$ 是 $\max(n-k,0)$。
由于 $j=i-k+n$，当 $i=m-1$ 时 $j$ 取到最大值 $m + n - 1 - k$，但这个数不能超过 $n-1$，所以最大的 $j$ 是 $\min(m + n - 1 - k, n - 1)$。

然后就可以模拟了：

枚举 $k=1,2,3,\dots,m+n-1$。
把对角线的元素存入列表 $a$ 中。
如果最小的 $j$ 大于 $0$，说明我们在主对角线右上，升序排序；否则降序排序。
把 $a$ 按顺序原样放回对角线中。

具体请看视频讲解，欢迎点赞关注~

###py

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        # 第一排在右上，最后一排在左下
        # 每排从左上到右下
        # 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
        for k in range(1, m + n):
            # 核心：计算 j 的最小值和最大值
            min_j = max(n - k, 0)  # i=0 的时候，j=n-k，但不能是负数
            max_j = min(m + n - 1 - k, n - 1)  # i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
            a = [grid[k + j - n][j] for j in range(min_j, max_j + 1)]  # 根据 k 的定义得 i=k+j-n
            a.sort(reverse = min_j==0)
            for j, val in zip(range(min_j, max_j + 1), a):
                grid[k + j - n][j] = val
        return grid

###java

class Solution {
    public int[][] sortMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 第一排在右上，最后一排在左下
        // 每排从左上到右下
        // 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
        for (int k = 1; k < m + n; k++) {
            // 核心：计算 j 的最小值和最大值
            int minJ = Math.max(n - k, 0); // i=0 的时候，j=n-k，但不能是负数
            int maxJ = Math.min(m + n - 1 - k, n - 1); // i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
            List<Integer> a = new ArrayList<>(maxJ - minJ + 1); // 预分配空间
            for (int j = minJ; j <= maxJ; j++) {
                a.add(grid[k + j - n][j]); // 根据 k 的定义得 i=k+j-n
            }
            a.sort(minJ > 0 ? null : Comparator.reverseOrder());
            for (int j = minJ; j <= maxJ; j++) {
                grid[k + j - n][j] = a.get(j - minJ);
            }
        }
        return grid;
    }
}

###cpp

class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 第一排在右上，最后一排在左下
        // 每排从左上到右下
        // 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
        for (int k = 1; k < m + n; k++) {
            // 核心：计算 j 的最小值和最大值
            int min_j = max(n - k, 0); // i=0 的时候，j=n-k，但不能是负数
            int max_j = min(m + n - 1 - k, n - 1); // i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
            vector<int> a;
            for (int j = min_j; j <= max_j; j++) {
                a.push_back(grid[k + j - n][j]); // 根据 k 的定义得 i=k+j-n
            }
            if (min_j > 0) { // 右上角三角形
                ranges::sort(a);
            } else { // 左下角三角形（包括中间对角线）
                ranges::sort(a, greater<int>());
            }
            for (int j = min_j; j <= max_j; j++) {
                grid[k + j - n][j] = a[j - min_j];
            }
        }
        return grid;
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))
#define MAX(a, b) ((b) > (a) ? (b) : (a))

int cmp_less(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int cmp_greater(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

int** sortMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    int m = gridSize, n = gridColSize[0];
    int* a = malloc(MIN(m, n) * sizeof(int));

    for (int k = 1; k < m + n; k++) {
        int min_j = MAX(n - k, 0); // i=0 时 j=n-k，但不能是负数
        int max_j = MIN(m + n - 1 - k, n - 1); // i=m-1 时 j=m+n-1-k，但不能超过 n-1

        int idx = 0;
        for (int j = min_j; j <= max_j; j++) {
            a[idx++] = grid[k + j - n][j]; // 根据 k 的定义 i=k+j-n
        }

        qsort(a, max_j - min_j + 1, sizeof(int), min_j > 0 ? cmp_less : cmp_greater);

        idx = 0;
        for (int j = min_j; j <= max_j; j++) {
            grid[k + j - n][j] = a[idx++];
        }
    }

    free(a);
    *returnSize = m;
    *returnColumnSizes = malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) {
        (*returnColumnSizes)[i] = n;
    }
    return grid;
}

###go

func sortMatrix(grid [][]int) [][]int {
m, n := len(grid), len(grid[0])
// 第一排在右上，最后一排在左下
// 每排从左上到右下
// 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
for k := 1; k < m+n; k++ {
// 核心：计算 j 的最小值和最大值
minJ := max(n-k, 0)       // i=0 的时候，j=n-k，但不能是负数
maxJ := min(m+n-1-k, n-1) // i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
a := []int{}
for j := minJ; j <= maxJ; j++ {
a = append(a, grid[k+j-n][j]) // 根据 k 的定义得 i=k+j-n
}
if minJ > 0 { // 右上角三角形
slices.Sort(a)
} else { // 左下角三角形（包括中间对角线）
slices.SortFunc(a, func(a, b int) int { return b - a })
}
for j := minJ; j <= maxJ; j++ {
grid[k+j-n][j] = a[j-minJ]
}
}
return grid
}

###js

var sortMatrix = function(grid) {
    const m = grid.length, n = grid[0].length;
    // 第一排在右上，最后一排在左下
    // 每排从左上到右下
    // 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
    for (let k = 1; k < m + n; k++) {
        // 核心：计算 j 的最小值和最大值
        const minJ = Math.max(n - k, 0); // i=0 的时候，j=n-k，但不能是负数
        const maxJ = Math.min(m + n - 1 - k, n - 1); // i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
        const a = [];
        for (let j = minJ; j <= maxJ; j++) {
            a.push(grid[k + j - n][j]); // 根据 k 的定义得 i=k+j-n
        }
        if (minJ > 0) { // 右上角三角形
            a.sort((x, y) => x - y);
        } else { // 左下角三角形（包括中间对角线）
            a.sort((x, y) => y - x);
        }
        for (let j = minJ; j <= maxJ; j++) {
            grid[k + j - n][j] = a[j - minJ];
        }
    }
    return grid;
};

###rust

impl Solution {
    pub fn sort_matrix(mut grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = grid.len();
        let n = grid[0].len();
        // 第一排在右上，最后一排在左下
        // 每排从左上到右下
        // 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
        for k in 1..m + n {
            // 核心：计算 j 的最小值和最大值
            let min_j = n.saturating_sub(k); // i=0 的时候，j=n-k，但不能是负数
            let max_j = (m + n - 1 - k).min(n - 1);
            let mut a = vec![];
            for j in min_j..=max_j {
                a.push(grid[k + j - n][j]); // 根据 k 的定义得 i=k+j-n
            }
            if min_j > 0 { // 右上角三角形
                a.sort_unstable();
            } else { // 左下角三角形（包括中间对角线）
                a.sort_unstable_by(|x, y| y.cmp(x));
            }
            for j in min_j..=max_j {
                grid[k + j - n][j] = a[j - min_j];
            }
        }
        grid
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2\log n)$，其中 $n$ 为 $\textit{grid}$ 的行数和列数。执行 $\mathcal{O}(n)$ 次时间复杂度为 $\mathcal{O}(n\log n)$ 的排序。
空间复杂度：$\mathcal{O}(n)$。

相似题目

分类题单

如何科学刷题？

我的题解精选（已分类）

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

记忆化搜索+最优性剪枝（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年2月16日 13:37

想象有一个人在网格图上移动，按照题目要求，移动经过的值必须为 $1,2,0,2,0,\dots$

由于至多转弯一次，所以移动路径不会形成环，可以写一个记忆化搜索，模拟人在网格图上的移动。

定义 $\textit{dfs}(i,j,k,\textit{canTurn},\textit{target})$ 表示在如下约束下的最长移动步数。

上一步的位置在 $(i,j)$。（定义成上一步，方便编程实现）
移动方向为 $\textit{DIRS}[k]$，其中 $\textit{DIRS}$ 是一个长为 $4$ 的方向数组。
是否可以右转，用布尔值 $\textit{canTurn}$ 表示。
当前位置的目标值必须等于 $\textit{target}$。

转移：

设 $(i',j')$ 是从 $(i,j)$ 向 $\textit{DIRS}[k]$ 方向移动一步后的位置。
直行：递归到 $\textit{dfs}(i',j',k,\textit{canTurn}, 2-\textit{target})$。这里用 $2-\textit{target}$ 来实现 $2$ 和 $0$ 的切换。也可以写成 $\textit{target}\oplus 2$。
右转：如果 $\textit{canTurn} = \texttt{true}$，那么递归到 $\textit{dfs}(i',j',(k+1)\bmod 4, \texttt{false}, 2-\textit{target})$。其中 $(k+1)\bmod 4$ 表示环形数组 $\textit{DIRS}$ 的下一个元素的下标。如果 $k<3$，那么 $k$ 更新为 $k+1$；否则 $k$ 更新为 $0$。
返回二者的最大值加一。其中加一表示走了一步。

递归边界：

出界，返回 $0$。
如果 $\textit{grid}[i'][j']\ne \textit{target}$，返回 $0$。

递归入口：

如果 $\textit{grid}[i][j]=1$，那么枚举 $k=0,1,2,3$，递归 $\textit{dfs}(i,j,k,\texttt{true},2)$。其中 $2$ 是因为下一步的值必须是 $2$。

计算所有 $\textit{dfs}(i,j,k,\texttt{true},2)+1$ 的最大值，即为答案。

⚠注意：$\textit{target}$ 无需记忆化，因为知道 $(i,j)$ 就间接知道 $\textit{target}$ 是多少，代码只是为了方便实现，额外传入了 $\textit{target}$。

关于记忆化搜索的原理，请看动态规划入门：从记忆化搜索到递推【基础算法精讲 17】。

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

优化前

###py

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        DIRS = (1, 1), (1, -1), (-1, -1), (-1, 1)
        m, n = len(grid), len(grid[0])

        # 上一步在 (i,j)，移动方向为 DIRS[k]，是否可以右转，当前位置目标值
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（一行代码实现记忆化）
        def dfs(i: int, j: int, k: int, can_turn: bool, target: int) -> int:
            i += DIRS[k][0]
            j += DIRS[k][1]
            if not (0 <= i < m and 0 <= j < n) or grid[i][j] != target:
                return 0
            res = dfs(i, j, k, can_turn, 2 - target)  # 直行
            if can_turn:
                res = max(res, dfs(i, j, (k + 1) % 4, False, 2 - target))  # 右转
            return res + 1  # 算上当前位置

        ans = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    # 枚举起始方向
                    for k in range(4):
                        ans = max(ans, dfs(i, j, k, True, 2) + 1)
        return ans

###java

class Solution {
    private static final int[][] DIRS = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

    public int lenOfVDiagonal(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 数组维度太多影响效率，这里把 k 和 canTurn 压缩成一个 int
        int[][][] memo = new int[m][n][1 << 3];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) { // 枚举起始方向
                        ans = Math.max(ans, dfs(i, j, k, 1, 2, grid, memo) + 1);
                    }
                }
            }
        }
        return ans;
    }

    // 上一步在 (i,j)，移动方向为 DIRS[k]，是否可以右转，当前位置目标值
    private int dfs(int i, int j, int k, int canTurn, int target, int[][] grid, int[][][] memo) {
        i += DIRS[k][0];
        j += DIRS[k][1];
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != target) {
            return 0;
        }
        int mask = k << 1 | canTurn;
        if (memo[i][j][mask] > 0) { // 之前计算过
            return memo[i][j][mask];
        }
        int res = dfs(i, j, k, canTurn, 2 - target, grid, memo); // 直行
        if (canTurn == 1) {
            res = Math.max(res, dfs(i, j, (k + 1) % 4, 0, 2 - target, grid, memo)); // 右转
        }
        return memo[i][j][mask] = res + 1; // 算上当前位置
    }
}

###cpp

class Solution {
    static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector<array<array<int, 2>, 4>>(n));

        // 上一步在 (i,j)，移动方向为 DIRS[k]，是否可以右转，当前位置目标值
        auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int {
            i += DIRS[k][0];
            j += DIRS[k][1];
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target) {
                return 0;
            }
            int& res = memo[i][j][k][can_turn]; // 注意这里是引用
            if (res) { // 之前计算过
                return res;
            }
            res = dfs(i, j, k, can_turn, 2 - target); // 直行
            if (can_turn) {
                res = max(res, dfs(i, j, (k + 1) % 4, false, 2 - target)); // 右转
            }
            return ++res; // 算上当前位置
        };

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) { // 枚举起始方向
                        ans = max(ans, dfs(i, j, k, true, 2) + 1);
                    }
                }
            }
        }
        return ans;
    }
};

###go

var DIRS = [4][2]int{{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}

func lenOfVDiagonal(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
memo := make([][][4][2]int, m)
for i := range memo {
memo[i] = make([][4][2]int, n)
}

// 上一步在 (i,j)，移动方向为 DIRS[k]，是否可以右转，当前位置目标值
var dfs func(int, int, int, int, int) int
dfs = func(i, j, k, canTurn, target int) (res int) {
i += DIRS[k][0]
j += DIRS[k][1]
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target {
return
}
p := &memo[i][j][k][canTurn]
if *p > 0 { // 之前计算过
return *p
}
defer func() { *p = res }() // 记忆化
res = dfs(i, j, k, canTurn, 2-target) // 直行
if canTurn == 1 {
res = max(res, dfs(i, j, (k+1)%4, 0, 2-target)) // 右转
}
return res + 1 // 算上当前位置
}

for i, row := range grid {
for j, x := range row {
if x == 1 {
for k := range 4 { // 枚举起始方向
ans = max(ans, dfs(i, j, k, 1, 2)+1)
}
}
}
}
return
}

最优性剪枝

优化一

在递归之前，如果发现即使走到底，移动步数也不会比目前算出的 $\textit{ans}$ 更大，那么不递归。

看图，设当前在 $(i,j)$：

如果一开始往右下走，无论是否右转，每一步都在往下走，所以至多走 $m-i$ 步。
如果一开始往左下走，无论是否右转，每一步都在往左走，所以至多走 $j+1$ 步。
如果一开始往左上走，无论是否右转，每一步都在往上走，所以至多走 $i+1$ 步。
如果一开始往右上走，无论是否右转，每一步都在往右走，所以至多走 $n-j$ 步。

如果理论最大移动步数 $\textit{mx}$ 大于 $\textit{ans}$，那么递归，否则不递归。

优化二

同理，在递归中，如果要右转，可以先判断继续走的理论最大值是否大于 $\textit{res}$，如果大于则递归，否则不递归。

###py

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        DIRS = (1, 1), (1, -1), (-1, -1), (-1, 1)
        m, n = len(grid), len(grid[0])

        @cache
        def dfs(i: int, j: int, k: int, can_turn: bool, target: int) -> int:
            i += DIRS[k][0]
            j += DIRS[k][1]
            if not (0 <= i < m and 0 <= j < n) or grid[i][j] != target:
                return 0
            res = dfs(i, j, k, can_turn, 2 - target)
            if can_turn:
                maxs = (m - i - 1, j, i, n - j - 1)  # 理论最大值（走到底）
                k = (k + 1) % 4
                # 优化二：如果理论最大值没有超过 res，那么不递归
                if maxs[k] > res:
                    res = max(res, dfs(i, j, k, False, 2 - target))
            return res + 1

        ans = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x != 1:
                    continue
                maxs = (m - i, j + 1, i + 1, n - j)  # 理论最大值（走到底）
                for k, mx in enumerate(maxs):  # 枚举起始方向
                    # 优化一：如果理论最大值没有超过 ans，那么不递归
                    if mx > ans:
                        ans = max(ans, dfs(i, j, k, True, 2) + 1)
        return ans

###java

class Solution {
    private static final int[][] DIRS = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

    public int lenOfVDiagonal(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 开太多维度影响效率，这里把 k 和 canTurn 压缩成一个 int
        int[][][] memo = new int[m][n][1 << 3];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) {
                    continue;
                }
                int[] maxs = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
                for (int k = 0; k < 4; k++) { // 枚举起始方向
                    if (maxs[k] > ans) { // 优化一：如果理论最大值没有超过 ans，那么不递归
                        ans = Math.max(ans, dfs(i, j, k, 1, 2, grid, memo) + 1);
                    }
                }
            }
        }
        return ans;
    }

    private int dfs(int i, int j, int k, int canTurn, int target, int[][] grid, int[][][] memo) {
        i += DIRS[k][0];
        j += DIRS[k][1];
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != target) {
            return 0;
        }
        int mask = k << 1 | canTurn;
        if (memo[i][j][mask] > 0) {
            return memo[i][j][mask];
        }
        int res = dfs(i, j, k, canTurn, 2 - target, grid, memo);
        if (canTurn == 1) {
            int[] maxs = {grid.length - i - 1, j, i, grid[i].length - j - 1}; // 理论最大值（走到底）
            k = (k + 1) % 4;
            // 优化二：如果理论最大值没有超过 res，那么不递归
            if (maxs[k] > res) {
                res = Math.max(res, dfs(i, j, k, 0, 2 - target, grid, memo));
            }
        }
        return memo[i][j][mask] = res + 1;
    }
}

###cpp

class Solution {
    static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector<array<array<int, 2>, 4>>(n));

        auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int {
            i += DIRS[k][0];
            j += DIRS[k][1];
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target) {
                return 0;
            }
            int& res = memo[i][j][k][can_turn];
            if (res) {
                return res;
            }
            res = dfs(i, j, k, can_turn, 2 - target);
            if (can_turn) {
                int maxs[4] = {m - i - 1, j, i, n - j - 1}; // 理论最大值（走到底）
                k = (k + 1) % 4;
                // 优化二：如果理论最大值没有超过 res，那么不递归
                if (maxs[k] > res) {
                    res = max(res, dfs(i, j, k, false, 2 - target));
                }
            }
            return ++res;
        };

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) {
                    continue;
                }
                int maxs[4] = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
                for (int k = 0; k < 4; k++) { // 枚举起始方向
                    if (maxs[k] > ans) { // 优化一：如果理论最大值没有超过 ans，那么不递归
                        ans = max(ans, dfs(i, j, k, true, 2) + 1);
                    }
                }
            }
        }
        return ans;
    }
};

###go

var DIRS = [4][2]int{{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}

func lenOfVDiagonal(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
memo := make([][][4][2]int, m)
for i := range memo {
memo[i] = make([][4][2]int, n)
}

var dfs func(int, int, int, int, int) int
dfs = func(i, j, k, canTurn, target int) (res int) {
i += DIRS[k][0]
j += DIRS[k][1]
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target {
return
}
p := &memo[i][j][k][canTurn]
if *p > 0 {
return *p
}
defer func() { *p = res }()
res = dfs(i, j, k, canTurn, 2-target)
if canTurn == 1 {
maxs := [4]int{m - i - 1, j, i, n - j - 1} // 理论最大值（走到底）
k = (k + 1) % 4
// 优化二：如果理论最大值没有超过 res，那么不递归
if maxs[k] > res {
res = max(res, dfs(i, j, k, 0, 2-target))
}
}
return res + 1
}

for i, row := range grid {
for j, x := range row {
if x != 1 {
continue
}
maxs := [4]int{m - i, j + 1, i + 1, n - j} // 理论最大值（走到底）
for k, mx := range maxs { // 枚举起始方向
if mx > ans { // 优化一：如果理论最大值没有超过 ans，那么不递归
ans = max(ans, dfs(i, j, k, 1, 2)+1)
}
}
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{grid}$ 的行数和列数。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(mn)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(mn)$。
空间复杂度：$\mathcal{O}(mn)$。保存多少状态，就需要多少空间。

相似题目

更多相似题目，见下面动态规划题单的「二、网格图 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

简洁写法，O(n) 一次遍历（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2024年1月7日 12:46

设矩形长宽分别为 $x$ 和 $y$。

根据勾股定理，矩形对角线长度的平方为

$$
x^2+y^2
$$

根据题意，我们需要用双关键字比大小，找到最大的面积。

第一关键字是对角线长度，直接用其平方值。如果遍历到更大的长度，则覆盖矩形面积。
第二关键字是矩形面积，即 $x\cdot y$。如果遇到了和最长长度一样长的矩形，那么更新面积的最大值。

###py

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        return max((x * x + y * y, x * y) for x, y in dimensions)[1]

###java

class Solution {
    public int areaOfMaxDiagonal(int[][] dimensions) {
        int ans = 0, maxL = 0;
        for (int[] d : dimensions) {
            int x = d[0], y = d[1];
            int l = x * x + y * y;
            if (l > maxL || l == maxL && x * y > ans) {
                maxL = l;
                ans = x * y;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        pair<int, int> mx{};
        for (auto& d : dimensions) {
            int x = d[0], y = d[1];
            mx = max(mx, pair(x * x + y * y, x * y));
        }
        return mx.second;
    }
};

###c

int areaOfMaxDiagonal(int** dimensions, int dimensionsSize, int* dimensionsColSize) {
    int ans = 0, max_l = 0;
    for (int i = 0; i < dimensionsSize; i++) {
        int x = dimensions[i][0], y = dimensions[i][1];
        int l = x * x + y * y;
        if (l > max_l || l == max_l && x * y > ans) {
            max_l = l;
            ans = x * y;
        }
    }
    return ans;
}

###go

func areaOfMaxDiagonal(dimensions [][]int) (ans int) {
maxL := 0
for _, d := range dimensions {
x, y := d[0], d[1]
l := x*x + y*y
if l > maxL || l == maxL && x*y > ans {
maxL = l
ans = x * y
}
}
return
}

###js

var areaOfMaxDiagonal = function(dimensions) {
    let ans = 0, maxL = 0;
    for (const [x, y] of dimensions) {
        const l = x * x + y * y;
        if (l > maxL || l === maxL && x * y > ans) {
            maxL = l;
            ans = x * y;
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn area_of_max_diagonal(dimensions: Vec<Vec<i32>>) -> i32 {
        let mut mx = (0, 0);
        for d in dimensions {
            let x = d[0];
            let y = d[1];
            mx = mx.max((x * x + y * y, x * y));
        }
        mx.1
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{dimensions}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

滑动窗口（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年6月17日 14:40

删除后，子数组只有 $1$，也就是没有 $0$。那么删除之前呢？至多有一个 $0$。

所以问题相当于：

求最长子数组的长度（减一），满足子数组至多有一个 $0$。

子数组越短，包含的 $0$ 越少，越能满足要求；子数组越长，包含的 $0$ 越多，越无法满足要求。所以当子数组的右端点增大时，左端点也随之增大（或者不变），这符合滑动窗口模型。如果你不了解滑动窗口，请看视频【基础算法精讲 03】。

这个方法对于至多有 $k$ 个 $0$ 的题目，也是适用的。

⚠注意：删除之前的子数组长度是 $\textit{right}-\textit{left}+1$，由于题目一定要删除一个数（尤其是在全为 $1$ 的情况下，一定要删除一个 $1$），所以删除后的子数组长度是 $\textit{right}-\textit{left}$，用其更新答案的最大值。

###py

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        ans = cnt0 = left = 0
        for right, x in enumerate(nums):
            # 1. 入，nums[right] 进入窗口
            cnt0 += 1 - x  # 维护窗口中的 0 的个数
            while cnt0 > 1:  # 不符合题目要求
                # 2. 出，nums[left] 离开窗口
                cnt0 -= 1 - nums[left]  # 维护窗口中的 0 的个数
                left += 1
            # 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
            ans = max(ans, right - left)
        return ans

###java

class Solution {
    public int longestSubarray(int[] nums) {
        int ans = 0;
        int cnt0 = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            // 1. 入，nums[right] 进入窗口
            cnt0 += 1 - nums[right]; // 维护窗口中的 0 的个数
            while (cnt0 > 1) { // 不符合题目要求
                // 2. 出，nums[left] 离开窗口
                cnt0 -= 1 - nums[left]; // 维护窗口中的 0 的个数
                left++;
            }
            // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
            ans = Math.max(ans, right - left);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int ans = 0, cnt0 = 0, left = 0;
        for (int right = 0; right < nums.size(); right++) {
            // 1. 入，nums[right] 进入窗口
            cnt0 += 1 - nums[right]; // 维护窗口中的 0 的个数
            while (cnt0 > 1) { // 不符合题目要求
                // 2. 出，nums[left] 离开窗口
                cnt0 -= 1 - nums[left]; // 维护窗口中的 0 的个数
                left++;
            }
            // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
            ans = max(ans, right - left);
        }
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int longestSubarray(int* nums, int numsSize) {
    int ans = 0, cnt0 = 0, left = 0;
    for (int right = 0; right < numsSize; right++) {
        // 1. 入，nums[right] 进入窗口
        cnt0 += 1 - nums[right]; // 维护窗口中的 0 的个数
        while (cnt0 > 1) { // 不符合题目要求
            // 2. 出，nums[left] 离开窗口
            cnt0 -= 1 - nums[left]; // 维护窗口中的 0 的个数
            left++;
        }
        // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
        ans = MAX(ans, right - left);
    }
    return ans;
}

###go

func longestSubarray(nums []int) (ans int) {
    cnt0, left := 0, 0
    for right, x := range nums {
        // 1. 入，nums[right] 进入窗口
        cnt0 += 1 - x  // 维护窗口中的 0 的个数
        for cnt0 > 1 { // 不符合题目要求
            // 2. 出，nums[left] 离开窗口
            cnt0 -= 1 - nums[left] // 维护窗口中的 0 的个数
            left++
        }
        // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
        ans = max(ans, right-left)
    }
    return
}

###js

var longestSubarray = function(nums) {
    let ans = 0, cnt0 = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
        // 1. 入，nums[right] 进入窗口
        cnt0 += 1 - nums[right]; // 维护窗口中的 0 的个数
        while (cnt0 > 1) { // 不符合题目要求
            // 2. 出，nums[left] 离开窗口
            cnt0 -= 1 - nums[left]; // 维护窗口中的 0 的个数
            left++;
        }
        // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
        ans = Math.max(ans, right - left);
    }
    return ans;
};

###rust

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut cnt0 = 0;
        let mut left = 0;
        for (right, &x) in nums.iter().enumerate() {
            // 1. 入，nums[right] 进入窗口
            cnt0 += 1 - x; // 维护窗口中的 0 的个数
            while cnt0 > 1 {
                // 2. 出，nums[left] 离开窗口
                cnt0 -= 1 - nums[left]; // 维护窗口中的 0 的个数
                left += 1;
            }
            // 3. 更新答案，注意不是 right-left+1，因为我们要删掉一个数
            ans = ans.max(right - left);
        }
        ans as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。虽然写了个二重循环，但是内层循环中对 $\textit{left}$ 加一的总执行次数不会超过 $n$ 次，所以总的时间复杂度为 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(1)$。

相似题目

见下面滑动窗口题单的「§2.1 越短越合法/求最长/最大」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

寻找矩形的左右上下边界（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2024年6月23日 12:07

遍历 $\textit{grid}$：

找到最左最右的 $1$ 的列号，分别记作 $\textit{left},\textit{right}$，则矩形底边长至少为 $\textit{right}-\textit{left}+1$。
找到最上最下的 $1$ 的行号，分别记作 $\textit{top},\textit{bottom}$，则矩形高至少为 $\textit{bottom} - \textit{top} + 1$。

矩形面积至少为

$$
(\textit{right} - \textit{left} + 1) \cdot (\textit{bottom} - \textit{top} + 1)
$$

###py

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        left = top = inf
        right = bottom = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    left = min(left, j)
                    right = max(right, j)
                    top = min(top, i)
                    bottom = i
        return (right - left + 1) * (bottom - top + 1)

###java

class Solution {
    public int minimumArea(int[][] grid) {
        int left = Integer.MAX_VALUE;
        int right = 0;
        int top = Integer.MAX_VALUE;
        int bottom = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    left = Math.min(left, j);
                    right = Math.max(right, j);
                    top = Math.min(top, i);
                    bottom = i;
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);
    }
}

###cpp

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int left = INT_MAX, right = 0;
        int top = INT_MAX, bottom = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j]) {
                    left = min(left, j);
                    right = max(right, j);
                    top = min(top, i);
                    bottom = i;
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))
#define MAX(a, b) ((b) > (a) ? (b) : (a))

int minimumArea(int** grid, int gridSize, int* gridColSize) {
    int left = INT_MAX, right = 0;
    int top = INT_MAX, bottom = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j]) {
                left = MIN(left, j);
                right = MAX(right, j);
                top = MIN(top, i);
                bottom = i;
            }
        }
    }
    return (right - left + 1) * (bottom - top + 1);
}

###go

func minimumArea(grid [][]int) int {
left, right := math.MaxInt, 0
top, bottom := math.MaxInt, 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
left = min(left, j)
right = max(right, j)
top = min(top, i)
bottom = i
}
}
}
return (right - left + 1) * (bottom - top + 1)
}

###js

var minimumArea = function(grid) {
    let left = Infinity, right = 0;
    let top = Infinity, bottom = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j]) {
                left = Math.min(left, j);
                right = Math.max(right, j);
                top = Math.min(top, i);
                bottom = i;
            }
        }
    }
    return (right - left + 1) * (bottom - top + 1);
};

###rust

impl Solution {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let mut left = usize::MAX;
        let mut right = 0;
        let mut top = usize::MAX;
        let mut bottom = 0;
        for (i, row) in grid.into_iter().enumerate() {
            for (j, x) in row.into_iter().enumerate() {
                if x != 0 {
                    left = left.min(j);
                    right = right.max(j);
                    top = top.min(i);
                    bottom = i;
                }
            }
        }
        ((right - left + 1) * (bottom - top + 1)) as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{grid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

【图解】两种方法：枚举上下边界 / 单调栈（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年6月21日 09:43

方法一：枚举子矩形的上下边界

枚举子矩形的上下边界，统计每一列的 $1$ 的个数，把原问题「压缩」为一维数组上的问题。

在示例 2 中，假设现在枚举到子矩形的上边界为 $0$ 行，下边界为 $1$ 行，即 $\textit{mat}$ 的前两行。子矩形的高 $h=2$。

统计每一列的 $1$ 的个数，得到一个一维数组 $a=[0,2,2,1]$。我们要找的子矩形，就是 $a$ 的子数组。由于全 $1$ 子矩形的每一列都是 $1$，所以子数组的每一项都得是子矩形的高 $h=2$。问题变成：

统计 $a$ 的全 $h$ 子数组的数目。

做法同 2348. 全 0 子数组的数目。

代码实现时，外层循环枚举上边界，内层循环枚举下边界。当下边界 $\textit{bottom}$ 加一时，只需把每个 $a[j]$ 都增加相应的 $\textit{mat}[\textit{bottom}][j]$，无需整个重新统计。

###py

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        ans = 0
        for top in range(m):  # 枚举上边界
            a = [0] * n
            for bottom in range(top, m):  # 枚举下边界
                h = bottom - top + 1  # 高
                # 2348. 全 h 子数组的数目
                last = -1
                for j in range(n):
                    a[j] += mat[bottom][j]  # 把 bottom 这一行的值加到 a 中
                    if a[j] != h:
                        last = j  # 记录上一个非 h 元素的位置
                    else:
                        ans += j - last
        return ans

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int ans = 0;
        for (int top = 0; top < m; top++) { // 枚举上边界
            int[] a = new int[n];
            for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
                int h = bottom - top + 1; // 高
                // 2348. 全 h 子数组的数目
                int last = -1;
                for (int j = 0; j < n; j++) {
                    a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
                    if (a[j] != h) {
                        last = j; // 记录上一个非 h 元素的位置
                    } else {
                        ans += j - last;
                    }
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int ans = 0;
        for (int top = 0; top < m; top++) { // 枚举上边界
            vector<int> a(n);
            for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
                int h = bottom - top + 1; // 高
                // 2348. 全 h 子数组的数目
                int last = -1;
                for (int j = 0; j < n; j++) {
                    a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
                    if (a[j] != h) {
                        last = j; // 记录上一个非 h 元素的位置
                    } else {
                        ans += j - last;
                    }
                }
            }
        }
        return ans;
    }
};

###go

func numSubmat(mat [][]int) (ans int) {
    m, n := len(mat), len(mat[0])
    for top := range m { // 枚举上边界
        a := make([]int, n)
        for bottom := top; bottom < m; bottom++ { // 枚举下边界
            h := bottom - top + 1 // 高
            // 2348. 全 h 子数组的数目
            last := -1
            for j := range n {
                a[j] += mat[bottom][j] // 把 bottom 这一行的值加到 a 中
                if a[j] != h {
                    last = j // 记录上一个非 h 元素的位置
                } else {
                    ans += j - last
                }
            }
        }
    }
    return
}

复杂度分析

时间复杂度：$\mathcal{O}(m^2n)$，其中 $m$ 和 $n$ 分别为 $\textit{mat}$ 的行数和列数。
空间复杂度：$\mathcal{O}(n)$。

方法二：单调栈

前置题目：85. 最大矩形，接着我的题解继续讲。

枚举子矩形的右下角（枚举底边，枚举右边界），有多少个对应的子矩形？

举个例子。

在示例 2 中，当我们枚举到最后一行时，柱子高度为 $\textit{heights}=[1,3,3,0]$。然后枚举子矩形的右边界：

右边界为 $j=0$，子矩形只有 $1$ 个。
右边界为 $j=1$，子矩形分成两类：
- 左边界 $<1$。在右边界为 $j=0$ 时我们算出这有 $1$ 个，现在将其右边界扩展到 $j=1$，得到 $1$ 个新的子矩形。
- 左边界 $\ge 1$。左边界只能是 $1$，矩形高度有 $1,2,3$ 共 $3$ 种，有 $1\times 3=3$ 个子矩形。
右边界为 $j=2$，子矩形分成两类：
- 左边界 $<1$。在右边界为 $j=0$ 时我们算出这有 $1$ 个，现在将其右边界扩展到 $j=2$，得到 $1$ 个新的子矩形。
- 左边界 $\ge 1$。左边界可以是 $1,2$ 共 $2$ 种，矩形高度有 $1,2,3$ 共 $3$ 种，有 $2\times 3=6$ 个子矩形。
右边界为 $j=3$，高度为 $0$，没有子矩形。

一般地，用单调栈计算小于 $\textit{heights}[j]$ 的左边最近柱子的位置 $\textit{left}$，把子矩形分成两类：

左边界 $\le \textit{left}$。假设在右边界为 $j=\textit{left}$ 时我们算出这有 $f$ 个，现在将其右边界扩展到 $j$，得到 $f$ 个新的子矩形。
左边界 $> \textit{left}$。矩形左边界可以是 $\textit{left}+1,\textit{left}+2,\ldots,j$，共 $j-\textit{left}$ 种；矩形高度可以是 $1,2,\ldots,\textit{heights}[j]$，共 $\textit{heights}[j]$ 种。所以有 $(j-\textit{left})\cdot \textit{heights}[j]$ 个子矩形。
二者相加，就是右边界在 $j$ 的子矩形个数。加到答案中。

###py

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        heights = [0] * len(mat[0])
        ans = 0
        for row in mat:
            for j, x in enumerate(row):
                if x == 0:
                    heights[j] = 0
                else:
                    heights[j] += 1

            # (j, f, heights[j])
            st = [(-1, 0, -1)]  # 哨兵，方便处理 left=-1 的情况
            for j, h in enumerate(heights):
                while st[-1][2] >= h:
                    st.pop()
                left, f, _ = st[-1]
                # 计算底边为 row，右边界为 j 的子矩形个数
                # 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                # 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h
                ans += f
                st.append((j, f, h))
        return ans

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat[0].length;
        int[] heights = new int[n];
        int ans = 0;

        int[][] st = new int[n + 1][3]; // (j, f, heights[j])
        for (int[] row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    heights[j] = 0;
                } else {
                    heights[j]++;
                }
            }

            st[0][0] = st[0][2] = -1; // 哨兵，方便处理 left=-1 的情况
            int top = 0;
            for (int j = 0; j < n; j++) {
                int h = heights[j];
                while (st[top][2] >= h) {
                    top--; // 出栈
                }
                int left = st[top][0];
                int f = st[top][1];
                // 计算底边为 row，右边界为 j 的子矩形个数
                // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h;
                ans += f;
                top++;
                st[top][0] = j; // 入栈
                st[top][1] = f;
                st[top][2] = h;
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat[0].size();
        vector<int> heights(n);
        int ans = 0;

        for (auto& row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    heights[j] = 0;
                } else {
                    heights[j]++;
                }
            }

            stack<tuple<int, int, int>> st; // (j, f, heights[j])
            st.emplace(-1, 0, -1); // 哨兵，方便处理 left=-1 的情况
            for (int j = 0; j < n; j++) {
                int h = heights[j];
                while (get<2>(st.top()) >= h) {
                    st.pop();
                }
                auto [left, f, _] = st.top();
                // 计算底边为 row，右边界为 j 的子矩形个数
                // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h;
                ans += f;
                st.emplace(j, f, h);
            }
        }

        return ans;
    }
};

###go

func numSubmat(mat [][]int) (ans int) {
    heights := make([]int, len(mat[0]))
    for _, row := range mat {
        for j, x := range row {
            if x == 0 {
                heights[j] = 0
            } else {
                heights[j]++
            }
        }

        type tuple struct{ j, f, h int }
        st := []tuple{{-1, 0, -1}} // 哨兵，方便处理 left=-1 的情况
        for j, h := range heights {
            for st[len(st)-1].h >= h {
                st = st[:len(st)-1]
            }
            p := st[len(st)-1]
            left, f := p.j, p.f
            // 计算底边为 row，右边界为 j 的子矩形个数
            // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
            // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
            f += (j - left) * h
            ans += f
            st = append(st, tuple{j, f, h})
        }
    }
    return
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{mat}$ 的行数和列数。
空间复杂度：$\mathcal{O}(n)$。

相似题目

见下面单调栈题单的「二、矩形」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

【图解】动态规划，简洁写法（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年8月13日 12:25

思路启发：学习二维前缀和对于想出本题的转移方程有帮助。

整理上图中的结论。定义 $f_{i,j}$ 为右下角在 $(i,j)$ 的全 $1$ 正方形的最大边长。我们有

$$
f_{i,j} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i-1,j-1},f_{i-1,j},f_{i,j-1}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$

然而，当 $i=0$ 或者 $j=0$ 时，上式会产生负数下标 $-1$。

为避免出现负数下标，可以在 $f$ 矩阵的最上边添加一行 $0$，最左边添加一列 $0$，对应下标出界的状态（正方形的最大边长为 $0$）。

由于修改了 $f$，状态转移方程中的 $f$ 的下标要加一，即

$$
f_{i+1,j+1} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i,j},f_{i,j+1},f_{i+1,j}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$

注意 $\textit{matrix}$ 的下标是不用变的，因为我们只是在 $f$ 矩阵的上边和左边插入了 $0$，所以只有 $f$ 的下标受此影响需要加一。

初始值 $f_{0,j} = f_{i,0} = 0$。

根据图中的结论（个数等于最大边长），答案为整个 $f$ 矩阵的元素和。

优化前

###py

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                if x:
                    f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1
        return sum(map(sum, f))

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] f = new int[m + 1][n + 1];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] > 0) {
                    f[i + 1][j + 1] = Math.min(Math.min(f[i][j], f[i][j + 1]), f[i + 1][j]) + 1;
                    ans += f[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector f(m + 1, vector<int>(n + 1));
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]) {
                    f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1;
                    ans += f[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
};

###go

func countSquares(matrix [][]int) (ans int) {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i, row := range matrix {
for j, x := range row {
if x > 0 {
f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1
ans += f[i+1][j+1]
}
}
}
return
}

优化

直接把 $\textit{matrix}$ 当作 $f$，原地修改。

###py

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                if x and i and j:
                    row[j] += min(matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1])
        return sum(map(sum, matrix))

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            for (int j = 0; j < row.length; j++) {
                if (row[j] > 0 && i > 0 && j > 0) {
                    row[j] += Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), row[j - 1]);
                }
                ans += row[j];
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.size(); i++) {
            auto& row = matrix[i];
            for (int j = 0; j < row.size(); j++) {
                if (i && j && row[j]) {
                    row[j] += min({matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]});
                }
                ans += row[j];
            }
        }
        return ans;
    }
};

###go

func countSquares(matrix [][]int) (ans int) {
for i, row := range matrix {
for j, x := range row {
if x > 0 && i > 0 && j > 0 {
row[j] += min(matrix[i-1][j], matrix[i-1][j-1], row[j-1])
}
ans += row[j]
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{matrix}$ 的行数和列数。
空间复杂度：优化前 $\mathcal{O}(mn)$，优化后 $\mathcal{O}(1)$。

专题训练

见下面动态规划题单的「§7.5 子矩形 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

两种更具一般性的方法：滑动窗口/增量法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2022年7月24日 07:22

前言

本题做法很多，下面讲两个更具一般性的方法。

方法一：用滑动窗口思考

子数组越长，越可能包含非零元素，不满足题目要求；子数组越短，越可能全为 $0$，满足题目要求。我们枚举子数组的右端点，当右端点变大（子数组变长）的时候，子数组左端点要么不变，要么也变大。

不仅是本题，有这样性质的题目，都可以用滑动窗口解决，见滑动窗口【基础算法精讲 03】。

本题属于「越短越合法」型滑动窗口。由于题目的特殊性，有更简单的解决方法：

记录上一个非零数字的位置 $\textit{last}$。那么 $\textit{last}+1$ 就是窗口的左端点。
当子数组右端点在 $i$ 时，子数组左端点可以是 $\textit{last}+1,\textit{last}+2,\dots,i$，一共有 $i-\textit{last}$ 个，加入答案。

示例 1 的 $\textit{nums} = [1,3,0,0,2,0,0,4]$，当右端点在 $i=3$ 时，$\textit{last}=1$，我们找到了 $i-\textit{last}=2$ 个右端点在 $3$ 的全 $0$ 子数组，加入答案。

为了兼容 $\textit{nums}=[0,0,0,2,0,0]$ 这种一开始就是 $0$ 的情况，初始化 $\textit{last}=-1$。

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        last = -1
        for i, x in enumerate(nums):
            if x:
                last = i  # 记录上一个非 0 元素的位置
            else:
                ans += i - last
        return ans

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (x != 0) {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += i - last;
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += i - last;
            }
        }
        return ans;
    }
};

long long zeroFilledSubarray(int* nums, int numsSize) {
    long long ans = 0;
    int last = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i]) {
            last = i; // 记录上一个非 0 元素的位置
        } else {
            ans += i - last;
        }
    }
    return ans;
}

func zeroFilledSubarray(nums []int) (ans int64) {
last := -1
for i, x := range nums {
if x != 0 {
last = i // 记录上一个非 0 元素的位置
} else {
ans += int64(i - last)
}
}
return
}

var zeroFilledSubarray = function(nums) {
    let ans = 0;
    let last = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            last = i; // 记录上一个非 0 元素的位置
        } else {
            ans += i - last;
        }
    }
    return ans;
};

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut last = -1;
        for (i, x) in nums.into_iter().enumerate() {
            let i = i as i64;
            if x != 0 {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += (i - last) as i64;
            }
        }
        ans
    }
}

复杂度分析

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

方法二：增量法

遍历到 $\textit{nums}[i]=0$，现在来计算右端点为 $i$ 的全 $0$ 子数组的个数。

我们可以在右端点为 $i-1$ 的全 $0$ 子数组的末尾添加一个 $0$。比如右端点为 $i-1$ 的全 $0$ 子数组有 $5$ 个，那么在这 $5$ 个子数组的末尾添加 $\textit{nums}[i]=0$，再算上 $\textit{nums}[i]$ 单独组成一个长为 $1$ 的子数组，我们得到了 $5+1=6$ 个右端点为 $i$ 的全 $0$ 子数组，加入答案。

具体来说：

用一个计数器 $\textit{cnt}_0$ 统计遍历到的连续 $0$ 的个数。
如果 $\textit{nums}[i]\ne 0$，把计数器重置为 $0$。
否则，把 $\textit{cnt}_0$ 加一，表示右端点为 $i$ 的全 $0$ 子数组比右端点为 $i-1$ 的全 $0$ 子数组多一个。然后把 $\textit{cnt}_0$ 加到答案中。

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = cnt0 = 0
        for x in nums:
            if x:
                cnt0 = 0
            else:
                cnt0 += 1  # 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0
        return ans

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        int cnt0 = 0;
        for (int x : nums) {
            if (x != 0) {
                cnt0 = 0;
            } else {
                cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0;
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long ans = 0;
        int cnt0 = 0;
        for (int x : nums) {
            if (x) {
                cnt0 = 0;
            } else {
                cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0;
            }
        }
        return ans;
    }
};

long long zeroFilledSubarray(int* nums, int numsSize) {
    long long ans = 0;
    int cnt0 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i]) {
            cnt0 = 0;
        } else {
            cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
            ans += cnt0;
        }
    }
    return ans;
}

func zeroFilledSubarray(nums []int) (ans int64) {
cnt0 := 0
for _, x := range nums {
if x != 0 {
cnt0 = 0
} else {
cnt0++ // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += int64(cnt0)
}
}
return
}

var zeroFilledSubarray = function(nums) {
    let ans = 0;
    let cnt0 = 0;
    for (const x of nums) {
        if (x !== 0) {
            cnt0 = 0;
        } else {
            cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
            ans += cnt0;
        }
    }
    return ans;
};

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut cnt0 = 0;
        for x in nums {
            if x != 0 {
                cnt0 = 0;
            } else {
                cnt0 += 1; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0 as i64;
            }
        }
        ans
    }
}

复杂度分析

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

注：本题还有其他方法，例如找极大连续 $0$ 的长度，然后用等差数列计算。

相似题目

413. 等差数列划分

专题训练

方法一：滑动窗口题单的「§2.3.1 越短越合法」。

方法二：动态规划题单「§7.3 子数组 DP」的「思维扩展」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

滑动窗口优化 DP，简洁写法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年8月17日 07:20

寻找子问题

我们要解决的问题（原问题）是：

从 $0$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

用「枚举选哪个」思考，即枚举我们获得多少分：

有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $1$ 分，问题变成从 $1$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $2$ 分，问题变成从 $2$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $3$ 分，问题变成从 $3$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
……
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $\textit{maxPts}$ 分，问题变成从 $\textit{maxPts}$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

这些问题都是和原问题相似的、规模更小的子问题。

状态定义与状态转移方程

根据上面的讨论，定义 $f[i]$ 表示从 $i$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

在当前回合，我们等概率地发生以下 $\textit{\textit{maxPts}}$ 种事件：

获得 $1$ 分。问题变成从 $i+1$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+1]$。
获得 $2$ 分。问题变成从 $i+2$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+2]$。
获得 $3$ 分。问题变成从 $i+3$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+3]$。
……
获得 $\textit{maxPts}$ 分。问题变成从 $i+\textit{maxPts}$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+\textit{maxPts}]$。

由于上述 $\textit{\textit{maxPts}}$ 种事件互斥且等概率地被选择，因此最终到达闭区间 $[k,n]$ 的概率为上述 $\textit{\textit{maxPts}}$ 个状态值的平均值，即

$$
f[i] = \dfrac{f[i+1] + f[i+2] + f[i+3] + \dots + f[i+\textit{maxPts}]}{\textit{maxPts}}
$$

由于转移来源比 $i$ 大，所以要倒序枚举 $i$。

由于转移方程中的分子是一个长度固定为 $\textit{maxPts}$ 的连续子数组的元素和，所以可以用定长滑动窗口 $\mathcal{O}(1)$ 计算，原理讲解请看【套路】教你解决定长滑窗！适用于所有定长滑窗题目！

初始值：

当 $k\le i\le n$ 时，游戏结束，由于到达闭区间 $[k,n]$，所以 $f[i]=1$。
当 $i > n$ 时，游戏结束，由于在闭区间 $[k,n]$ 外，所以 $f[i]=0$。代码实现时，可以直接创建大小为 $n+1$ 的 $f$ 数组，下标出界就表示 $f[i]=0$。

答案：$f[0]$，即原问题。

答疑

问：为什么滑动窗口的计算顺序不是「入-计算-出」，而是「计算-入-出」？

答：当我们遍历到 $i$ 时，窗口的左端点是 $i+1$ 而不是 $i$。所以 $f[i]$ 并不在窗口中，得先把 $f[i]$ 计算出来，然后下个循环 $f[i]$ 才在窗口中。

注：$n$ 可以与 $k+\textit{maxPts}$ 取 $\min$，但测试发现这个优化不显著。

###py

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        f = [0.0] * (n + 1)
        s = 0.0
        for i in range(n, -1, -1):
            f[i] = 1.0 if i >= k else s / maxPts
            # 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            # 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i]
            if i + maxPts <= n:
                s -= f[i + maxPts]
        return f[0]

###java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        double[] f = new double[n + 1];
        double s = 0;
        for (int i = n; i >= 0; i--) {
            f[i] = i >= k ? 1 : s / maxPts;
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if (i + maxPts <= n) {
                s -= f[i + maxPts];
            }
        }
        return f[0];
    }
}

###cpp

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        vector<double> f(n + 1);
        double s = 0;
        for (int i = n; i >= 0; i--) {
            f[i] = i >= k ? 1 : s / maxPts;
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if (i + maxPts <= n) {
                s -= f[i + maxPts];
            }
        }
        return f[0];
    }
};

###c

double new21Game(int n, int k, int maxPts) {
    double* f = malloc((n + 1) * sizeof(double));
    double s = 0;

    for (int i = n; i >= 0; i--) {
        f[i] = i >= k ? 1 : s / maxPts;
        // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
        // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
        s += f[i];
        if (i + maxPts <= n) {
            s -= f[i + maxPts];
        }
    }

    double ans = f[0];
    free(f);
    return ans;
}

###go

func new21Game(n, k, maxPts int) float64 {
f := make([]float64, n+1)
s := 0.0
for i := n; i >= 0; i-- {
if i >= k {
f[i] = 1 // 初始值
} else {
f[i] = s / float64(maxPts)
}
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i+maxPts <= n {
s -= f[i+maxPts]
}
}
return f[0]
}

###js

var new21Game = function(n, k, maxPts) {
    const f = new Array(n + 1).fill(0);
    let s = 0;
    for (let i = n; i >= 0; i--) {
        f[i] = i >= k ? 1 : s / maxPts;
        // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
        // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
        s += f[i];
        if (i + maxPts <= n) {
            s -= f[i + maxPts];
        }
    }
    return f[0];
};

###rust

impl Solution {
    pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
        let n = n as usize;
        let k = k as usize;
        let max_pts = max_pts as usize;
        let mut f = vec![0.0; n + 1];
        let mut s = 0.0;
        for i in (0..=n).rev() {
            f[i] = if i >= k { 1.0 } else { s / max_pts as f64 };
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if i + max_pts <= n {
                s -= f[i + max_pts];
            }
        }
        f[0]
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面动态规划题单的「十五、概率/期望 DP」和「§11.1 前缀和优化 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

阅读视图

复杂度分析

专题训练

分类题单

分析

公式推导

优化前

复杂度分析

化简公式

复杂度分析

专题训练

分类题单

转化

上下界分析

枚举 k

复杂度分析

分类题单

写法一

写法二

复杂度分析

分类题单

复杂度分析

分类题单

写法一：使用浮点数

写法二：不使用浮点数

复杂度分析

专题训练

分类题单

前置题目

核心思路

实现细节

复杂度分析

专题训练

分类题单

复杂度分析

思考题

分类题单

复杂度分析

分类题单

复杂度分析

相似题目

分类题单

优化前

最优性剪枝

优化一

优化二

复杂度分析

相似题目

分类题单

复杂度分析

分类题单

复杂度分析

相似题目

分类题单

复杂度分析

分类题单

方法一：枚举子矩形的上下边界

复杂度分析

方法二：单调栈

复杂度分析

相似题目

分类题单

优化前

优化

复杂度分析

专题训练

分类题单

前言

方法一：用滑动窗口思考

复杂度分析

方法二：增量法

复杂度分析

相似题目

专题训练

分类题单

寻找子问题

状态定义与状态转移方程

答疑

复杂度分析

专题训练