两种方法：普通 DP / 值域线段树优化 DP（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2023年7月9日 12:09

一、寻找子问题

想一想，最后一步发生了什么？

最后一步，我们从某个满足条件的下标 $i$ 跳到了下标 $n-1$。

枚举满足条件的 $i$，问题变成：

从下标 $0$ 到达下标 $i$ 所需的最大跳跃次数。

这是和原问题相似的、规模更小的子问题，可以用递归解决。

注：从右往左思考，主要是方便把递归翻译成从左往右的递推。从左往右思考也是可以的。

二、状态定义与状态转移方程

根据上面的讨论，定义 $\textit{dfs}(j)$ 表示从下标 $0$ 到达下标 $j$ 所需的最大跳跃次数。

枚举满足 $0\le i<j$ 且 $|\textit{nums}[i]-\textit{nums}[j]|\le \textit{target}$ 的下标 $i$，问题变成从下标 $0$ 到达下标 $i$ 所需的最大跳跃次数，再加上从 $i$ 跳到 $j$ 的一次。

取最大值，得

$$
\textit{dfs}(j) = \max_{i} \textit{dfs}(i) + 1
$$

其中 $0\le i<j$ 且 $|\textit{nums}[i]-\textit{nums}[j]|\le \textit{target}$。

递归边界：

$\textit{dfs}(0)=0$。从 $0$ 到 $0$ 不用跳。
如果没有满足条件的 $i$，那么 $\textit{dfs}(j) = -\infty$。

递归入口：$\textit{dfs}(n-1)$，这是原问题，也是答案。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

关于记忆化搜索的原理，请看视频讲解动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(j: int) -> int:
            if j == 0:  # 起点
                return 0
            res = -inf
            for i in range(j):
                if abs(nums[i] - nums[j]) <= target:  # 可以从 i 跳到 j
                    res = max(res, dfs(i) + 1)
            return res

        ans = dfs(len(nums) - 1)  # 终点
        return -1 if ans < 0 else ans

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] memo = new int[n];
        int ans = dfs(n - 1, nums, target, memo);
        return ans < 0 ? -1 : ans;
    }

    private int dfs(int j, int[] nums, int target, int[] memo) {
        if (j == 0) { // 起点
            return 0;
        }

        if (memo[j] != 0) { // 之前计算过
            return memo[j];
        }

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < j; i++) {
            if (Math.abs(nums[i] - nums[j]) <= target) { // 可以从 i 跳到 j
                res = Math.max(res, dfs(i, nums, target, memo) + 1);
            }
        }
        memo[j] = res; // 记忆化
        return res;
    }
}

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> memo(n);

        auto dfs = [&](this auto&& dfs, int j) -> int {
            if (j == 0) { // 起点
                return 0;
            }

            int& res = memo[j]; // 注意这里是引用
            if (res) { // 之前计算过
                return res;
            }

            res = INT_MIN;
            for (int i = 0; i < j; i++) {
                if (abs(nums[i] - nums[j]) <= target) { // 可以从 i 跳到 j
                    res = max(res, dfs(i) + 1);
                }
            }
            return res;
        };

        int ans = dfs(n - 1); // 终点
        return ans < 0 ? -1 : ans;
    }
};

func maximumJumps(nums []int, target int) int {
n := len(nums)
memo := make([]int, n)

var dfs func(int) int
dfs = func(j int) int {
if j == 0 { // 起点
return 0
}

p := &memo[j]
if *p != 0 { // 之前计算过
return *p
}

res := math.MinInt
for i, x := range nums[:j] {
if abs(x-nums[j]) <= target { // 可以从 i 跳到 j
res = max(res, dfs(i)+1)
}
}
*p = res // 记忆化
return res
}

ans := dfs(n - 1) // 终点
if ans < 0 {
return -1
}
return ans
}

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

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $\textit{nums}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n)$，单个状态的计算时间为 $\mathcal{O}(n)$，所以总的时间复杂度为 $\mathcal{O}(n^2)$。
空间复杂度：$\mathcal{O}(n)$。保存多少状态，就需要多少空间。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[j]$ 的定义和 $\textit{dfs}(j)$ 的定义是完全一样的，都表示从下标 $0$ 到达下标 $j$ 所需的最大跳跃次数。

相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：

$$
f[j] = \max_{i} f[i] + 1
$$

其中 $0\le i<j$ 且 $|\textit{nums}[i]-\textit{nums}[j]|\le \textit{target}$。

如果没有满足条件的 $i$，那么 $f[j] = -\infty$。

初始值 $f[0]=0$，翻译自递归边界 $\textit{dfs}(0)=0$。

答案为 $f[n-1]$，翻译自递归入口 $\textit{dfs}(n-1)$。

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [-inf] * n
        f[0] = 0
        for j in range(1, n):
            for i in range(j):
                if abs(nums[i] - nums[j]) <= target:  # 可以从 i 跳到 j
                    f[j] = max(f[j], f[i] + 1)
        return -1 if f[-1] < 0 else f[-1]

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] f = new int[n];
        for (int j = 1; j < n; j++) {
            f[j] = Integer.MIN_VALUE;
            for (int i = 0; i < j; i++) {
                if (Math.abs(nums[i] - nums[j]) <= target) { // 可以从 i 跳到 j
                    f[j] = Math.max(f[j], f[i] + 1);
                }
            }
        }
        return f[n - 1] < 0 ? -1 : f[n - 1];
    }
}

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(n, INT_MIN);
        f[0] = 0;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (abs(nums[i] - nums[j]) <= target) { // 可以从 i 跳到 j
                    f[j] = max(f[j], f[i] + 1);
                }
            }
        }
        return f[n - 1] < 0 ? -1 : f[n - 1];
    }
};

func maximumJumps(nums []int, target int) int {
n := len(nums)
f := make([]int, n)

for j := 1; j < n; j++ {
f[j] = math.MinInt
for i, x := range nums[:j] {
if abs(x-nums[j]) <= target { // 可以从 i 跳到 j
f[j] = max(f[j], f[i]+1)
}
}
}

if f[n-1] < 0 {
return -1
}
return f[n-1]
}

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

复杂度分析

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

五、值域线段树优化 DP

如果 $n=10^5$，上面的做法就超时了。

遍历到 $\textit{nums}[j]$ 时，我们需要知道满足 $\textit{nums}[j]-\textit{target} \le \textit{nums}[i] \le \textit{nums}[j]+\textit{target}$ 的最大的 $f[i]$。

这可以用一棵值域线段树维护。线段树的区间是值域区间，例如区间 $[20,23]$ 指的是 $\textit{nums}$ 中的元素 $20,21,22,23$。线段树的每个节点保存的是值域区间对应的最大的 $f[i]$。例如 $\textit{nums}[4]=20$ 且 $f[4] = 3$，那么线段树维护的位置 $20$ 更新为 $3$。

如此一来，满足 $\textit{nums}[j]-\textit{target} \le \textit{nums}[i] \le \textit{nums}[j]+\textit{target}$ 的最大的 $f[i]$，可以通过线段树的区间最值查询得到。

# 完整的线段树模板见 https://leetcode.cn/circle/discuss/mOr1u6/
class SegmentTree:
    def __init__(self, n: int) -> None:
        self.t = [-inf] * (2 << (n - 1).bit_length())

    def update(self, node: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:  # 叶子
            self.t[node] = val
            return
        m = (l + r) // 2
        if i <= m:  # i 在左子树
            self.update(node * 2, l, m, i, val)
        else:  # i 在右子树
            self.update(node * 2 + 1, m + 1, r, i, val)
        self.t[node] = max(self.t[node * 2], self.t[node * 2 + 1])

    def query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内
            return self.t[node]
        m = (l + r) // 2
        if qr <= m:  # [ql, qr] 在左子树
            return self.query(node * 2, l, m, ql, qr)
        if ql > m:  # [ql, qr] 在右子树
            return self.query(node * 2 + 1, m + 1, r, ql, qr)
        return max(self.query(node * 2, l, m, ql, qr), self.query(node * 2 + 1, m + 1, r, ql, qr))


class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        # 去重排序，便于离散化
        sorted_nums = sorted(set(nums))

        n = len(nums)
        m = len(sorted_nums)
        t = SegmentTree(m)  # 值域线段树

        # nums[0] 对应的 f[0] = 0
        t.update(1, 0, m - 1, bisect_left(sorted_nums, nums[0]), 0)

        for j in range(1, n):
            l = bisect_left(sorted_nums, nums[j] - target)       # >= nums[j]-target 的第一个数
            r = bisect_right(sorted_nums, nums[j] + target) - 1  # <= nums[j]+target 的最后一个数
            # t.query 返回满足 nums[j]-target <= nums[i] <= nums[j]+target 的最大的 f[i]
            fj = t.query(1, 0, m - 1, l, r) + 1
            t.update(1, 0, m - 1, bisect_left(sorted_nums, nums[j]), fj)

        return -1 if fj < 0 else fj

class Solution {
    // 完整的线段树模板见 https://leetcode.cn/circle/discuss/mOr1u6/
    private int[] tree;

    private void update(int node, int l, int r, int i, int val) {
        if (l == r) { // 叶子
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) { // i 在左子树
            update(node * 2, l, m, i, val);
        } else { // i 在右子树
            update(node * 2 + 1, m + 1, r, i, val);
        }
        tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
    }

    private int query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node];
        }
        int m = (l + r) / 2;
        if (qr <= m) { // [ql, qr] 在左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 在右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        return Math.max(query(node * 2, l, m, ql, qr), query(node * 2 + 1, m + 1, r, ql, qr));
    }

    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] sorted = nums.clone(); // 用于离散化
        Arrays.sort(sorted);

        tree = new int[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        Arrays.fill(tree, Integer.MIN_VALUE);

        // nums[0] 对应的 f[0] = 0
        update(1, 0, n - 1, lowerBound(sorted, nums[0]), 0);

        for (int j = 1; ; j++) {
            int l = lowerBound(sorted, (long) nums[j] - target);         // >= nums[j]-target 的第一个数
            int r = lowerBound(sorted, (long) nums[j] + target + 1) - 1; // <= nums[j]+target 的最后一个数
            // query 返回满足 nums[j]-target <= nums[i] <= nums[j]+target 的最大的 f[i]
            int fj = query(1, 0, n - 1, l, r) + 1;
            if (j == n - 1) {
                return fj < 0 ? -1 : fj;
            }
            update(1, 0, n - 1, lowerBound(sorted, nums[j]), fj);
        }
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(int[] nums, long target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

// 完整的线段树模板见 https://leetcode.cn/circle/discuss/mOr1u6/
class SegmentTree {
    vector<int> tree;

public:
    SegmentTree(int n) : tree(2 << bit_width(n - 1u), INT_MIN) {}

    void update(int node, int l, int r, int i, int val) {
        if (l == r) { // 叶子
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) { // i 在左子树
            update(node * 2, l, m, i, val);
        } else { // i 在右子树
            update(node * 2 + 1, m + 1, r, i, val);
        }
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    int query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node];
        }
        int m = (l + r) / 2;
        if (qr <= m) { // [ql, qr] 在左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 在右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        return max(query(node * 2, l, m, ql, qr), query(node * 2 + 1, m + 1, r, ql, qr));
    }
};

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        // 排序去重，便于离散化
        auto sorted = nums;
        ranges::sort(sorted);
        sorted.erase(ranges::unique(sorted).begin(), sorted.end());

        int n = nums.size();
        int m = sorted.size();

        SegmentTree t(m); // 值域线段树

        // nums[0] 对应的 f[0] = 0
        int pos = ranges::lower_bound(sorted, nums[0]) - sorted.begin();
        t.update(1, 0, m - 1, pos, 0);

        long long tar = target;
        for (int j = 1; ; j++) {
            int l = ranges::lower_bound(sorted, nums[j] - tar) - sorted.begin();     // >= nums[j]-target 的第一个数
            int r = ranges::upper_bound(sorted, nums[j] + tar) - sorted.begin() - 1; // <= nums[j]+target 的最后一个数
            // t.query 返回满足 nums[j]-target <= nums[i] <= nums[j]+target 的最大的 f[i]
            int fj = t.query(1, 0, m - 1, l, r) + 1;
            if (j == n - 1) {
                return fj < 0 ? -1 : fj;
            }
            pos = ranges::lower_bound(sorted, nums[j]) - sorted.begin();
            t.update(1, 0, m - 1, pos, fj);
        }
    }
};

// 完整的线段树模板见 https://leetcode.cn/circle/discuss/mOr1u6/
type seg []int

func (t seg) update(node, l, r, i, val int) {
if l == r { // 叶子
t[node] = val
return
}
m := (l + r) / 2
if i <= m { // i 在左子树
t.update(node*2, l, m, i, val)
} else { // i 在右子树
t.update(node*2+1, m+1, r, i, val)
}
t[node] = max(t[node*2], t[node*2+1])
}

func (t seg) query(node, l, r, ql, qr int) int {
if ql <= l && r <= qr { // 当前子树完全在 [ql, qr] 内
return t[node]
}
m := (l + r) / 2
if qr <= m { // [ql, qr] 在左子树
return t.query(node*2, l, m, ql, qr)
}
if ql > m { // [ql, qr] 在右子树
return t.query(node*2+1, m+1, r, ql, qr)
}
return max(t.query(node*2, l, m, ql, qr), t.query(node*2+1, m+1, r, ql, qr))
}

func maximumJumps(nums []int, target int) int {
// 排序去重，便于离散化
sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)

n := len(nums)
m := len(sorted)

t := make(seg, 2<<bits.Len(uint(m-1))) // 值域线段树
for i := range t {
t[i] = math.MinInt
}

// nums[0] 对应的 f[0] = 0
t.update(1, 0, m-1, sort.SearchInts(sorted, nums[0]), 0)

for j := 1; ; j++ {
l := sort.SearchInts(sorted, nums[j]-target)       // >= nums[j]-target 的第一个数
r := sort.SearchInts(sorted, nums[j]+target+1) - 1 // <= nums[j]+target 的最后一个数
// t.query 返回满足 nums[j]-target <= nums[i] <= nums[j]+target 的最大的 f[i]
fj := t.query(1, 0, m-1, l, r) + 1
if j == n-1 {
if fj < 0 {
return -1
}
return fj
}
t.update(1, 0, m-1, sort.SearchInts(sorted, nums[j]), fj)
}
}

复杂度分析

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

相似题目

2407. 最长递增子序列 II

更多相似题目，见下面动态规划题单的「§11.4 树状数组/线段树优化 DP」和「专题：跳跃游戏」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

利用方向向量简化代码，O(1) 空间优化（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2021年6月27日 12:08

本题是模拟题，由于每一圈互相独立，可以分别处理。

对于每一圈：

从左上角开始，顺时针遍历这一圈，把遍历到的元素记录到一个数组 $a$ 中。
把 $a$ 循环左移 $k\bmod N$ 次，其中 $N$ 是数组 $a$ 的长度。这是因为，循环左移 $N$ 次等同于没有左移，循环左移 $N+1$ 次等同于循环左移 $1$ 次，依此类推，循环左移 $k$ 次等同于循环左移 $k\bmod N$ 次。
把 $a$ 中元素按照步骤 1 中的顺序，重新填回 $\textit{grid}$。

对于步骤 1，可以仿照 54. 螺旋矩阵的方法二，使用一个方向向量数组分别表示顺时针的右、下、左、上。对于最外圈，分别移动 $n-1,m-1,n-1,m-1$ 次；对于次外圈，分别移动 $n-3,m-3,n-3,m-3$ 次；依此类推。

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m0, n0 = len(grid), len(grid[0])

        # 从外到内枚举圈
        for i in range(min(m0, n0) // 2):
            m, n = m0 - i * 2, n0 - i * 2  # 这一圈的行数和列数
            x, y = i, i  # 这一圈的左上角
            a = []
            for dx, dy in DIRS:
                for _ in range(n - 1):
                    a.append(grid[x][y])
                    x += dx
                    y += dy
                m, n = n, m  # 见 54. 螺旋矩阵 我的题解

            shift = k % len(a)
            a = a[shift:] + a[:shift]

            # 注意此时 (x, y) 又回到了左上角
            j = 0
            for dx, dy in DIRS:
                for _ in range(n - 1):
                    grid[x][y] = a[j]
                    j += 1
                    x += dx
                    y += dy
                m, n = n, m

        return grid

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上

    public int[][] rotateGrid(int[][] grid, int k) {
        int m0 = grid.length, n0 = grid[0].length;
        List<Integer> a = new ArrayList<>((m0 + n0 - 2) * 2); // 预分配空间

        // 从外到内枚举圈
        for (int i = 0; i < Math.min(m0, n0) / 2; i++) {
            int m = m0 - i * 2, n = n0 - i * 2; // 这一圈的行数和列数
            int x = i, y = i; // 这一圈的左上角
            a.clear();
            for (int[] dir : DIRS) {
                for (int t = 0; t < n - 1; t++) {
                    a.add(grid[x][y]);
                    x += dir[0];
                    y += dir[1];
                }
                int tmp = m; // 见 54. 螺旋矩阵 我的题解
                m = n;
                n = tmp; 
            }

            int shift = k % a.size();
            Collections.rotate(a, -shift);

            // 注意此时 (x, y) 又回到了左上角
            int j = 0;
            for (int[] dir : DIRS) {
                for (int t = 0; t < n - 1; t++) {
                    grid[x][y] = a.get(j++);
                    x += dir[0];
                    y += dir[1];
                }
                int temp = m;
                m = n;
                n = temp;
            }
        }

        return grid;
    }
}

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上

public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m0 = grid.size(), n0 = grid[0].size();
        vector<int> a;
        a.reserve((m0 + n0 - 2) * 2); // 预分配空间

        // 从外到内枚举圈
        for (int i = 0; i < min(m0, n0) / 2; i++) {
            int m = m0 - i * 2, n = n0 - i * 2; // 这一圈的行数和列数
            int x = i, y = i; // 这一圈的左上角
            a.resize(0);
            for (auto& [dx, dy] : DIRS) {
                for (int t = 0; t < n - 1; t++) {
                    a.push_back(grid[x][y]);
                    x += dx;
                    y += dy;
                }
                swap(m, n); // 见 54. 螺旋矩阵 我的题解
            }

            int shift = k % a.size();
            ranges::rotate(a, a.begin() + shift);

            // 注意此时 (x, y) 又回到了左上角
            int j = 0;
            for (auto& [dx, dy] : DIRS) {
                for (int t = 0; t < n - 1; t++) {
                    grid[x][y] = a[j++];
                    x += dx;
                    y += dy;
                }
                swap(m, n);
            }
        }

        return grid;
    }
};

var dirs = [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右下左上

func rotateGrid(grid [][]int, k int) [][]int {
m0, n0 := len(grid), len(grid[0])
a := make([]int, 0, (m0+n0-2)*2) // 预分配空间

// 从外到内枚举圈
for i := range min(m0, n0) / 2 {
m, n := m0-i*2, n0-i*2 // 这一圈的行数和列数
x, y := i, i // 这一圈的左上角
a = a[:0]
for _, dir := range dirs {
for range n - 1 {
a = append(a, grid[x][y])
x += dir[0]
y += dir[1]
}
m, n = n, m // 见 54. 螺旋矩阵 我的题解
}

shift := k % len(a)
a = append(a[shift:], a[:shift]...)

// 注意此时 (x, y) 又回到了左上角
j := 0
for _, dir := range dirs {
for range n - 1 {
grid[x][y] = a[j]
j++
x += dir[0]
y += dir[1]
}
m, n = n, m
}
}

return grid
}

复杂度分析

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

空间优化

利用 189. 轮转数组的技巧，可以做到 $\mathcal{O}(1)$ 空间。详见我的题解。

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m0, n0 = len(grid), len(grid[0])

        # 从外到内枚举圈
        for i in range(min(m0, n0) // 2):
            m, n = m0 - i * 2 - 1, n0 - i * 2 - 1  # 注意这里减一了

            # 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
            def index(p: int) -> Tuple[int, int]:
                # 左上角在 (i, i)
                if p < n:
                    return i, i + p
                if p < n + m:
                    return i + p - n, i + n
                if p < n * 2 + m:
                    return i + m, i - p + n * 2 + m
                return i - p + (n + m) * 2, i

            def reverse(l: int, r: int) -> None:
                while l < r:
                    x1, y1 = index(l)
                    x2, y2 = index(r)
                    grid[x1][y1], grid[x2][y2] = grid[x2][y2], grid[x1][y1]
                    l += 1
                    r -= 1

            # 189. 轮转数组（改成向左轮转）
            size = (m + n) * 2
            shift = k % size
            reverse(0, shift - 1)
            reverse(shift, size - 1)
            reverse(0, size - 1)

        return grid

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m0 = grid.length, n0 = grid[0].length;

        // 从外到内枚举圈
        for (int i = 0; i < Math.min(m0, n0) / 2; i++) {
            int m = m0 - i * 2 - 1, n = n0 - i * 2 - 1; // 注意这里减一了

            // 189. 轮转数组（改成向左轮转）
            int size = (m + n) * 2;
            int shift = k % size;
            reverse(grid, i, m, n, 0, shift - 1);
            reverse(grid, i, m, n, shift, size - 1);
            reverse(grid, i, m, n, 0, size - 1);
        }

        return grid;
    }

    private void reverse(int[][] grid, int i, int m, int n, int l, int r) {
        while (l < r) {
            int[] p1 = index(i, m, n, l);
            int[] p2 = index(i, m, n, r);
            int x1 = p1[0], y1 = p1[1];
            int x2 = p2[0], y2 = p2[1];

            int tmp = grid[x1][y1];
            grid[x1][y1] = grid[x2][y2];
            grid[x2][y2] = tmp;

            l++;
            r--;
        }
    }

    private int[] index(int i, int m, int n, int p) {
        // 左上角在 (i, i)
        if (p < n) {
            return new int[]{i, i + p};
        }
        if (p < n + m) {
            return new int[]{i + p - n, i + n};
        }
        if (p < n * 2 + m) {
            return new int[]{i + m, i - p + n * 2 + m};
        }
        return new int[]{i - p + (n + m) * 2, i};
    }
}

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m0 = grid.size(), n0 = grid[0].size();

        // 从外到内枚举圈
        for (int i = 0; i < min(m0, n0) / 2; i++) {
            int m = m0 - i * 2 - 1, n = n0 - i * 2 - 1; // 注意这里减一了

            // 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
            auto index = [&](int p) -> pair<int, int> {
                // 左上角在 (i, i)
                if (p < n) {
                    return {i, i + p};
                }
                if (p < n + m) {
                    return {i + p - n, i + n};
                }
                if (p < n * 2 + m) {
                    return {i + m, i - p + n * 2 + m};
                }
                return {i - p + (n + m) * 2, i};
            };

            auto reverse = [&](int l, int r) {
                while (l < r) {
                    auto [x1, y1] = index(l);
                    auto [x2, y2] = index(r);
                    swap(grid[x1][y1], grid[x2][y2]);
                    l++;
                    r--;
                }
            };

            // 189. 轮转数组（改成向左轮转）
            int size = (m + n) * 2;
            int shift = k % size;
            reverse(0, shift - 1);
            reverse(shift, size - 1);
            reverse(0, size - 1);
        }

        return grid;
    }
};

func rotateGrid(grid [][]int, k int) [][]int {
m0, n0 := len(grid), len(grid[0])

// 从外到内枚举圈
for i := range min(m0, n0) / 2 {
m, n := m0-i*2-1, n0-i*2-1 // 注意这里减一了

// 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
index := func(p int) (x, y int) {
// 左上角在 (i, i)
if p < n {
return i, i + p
}
if p < n+m {
return i + p - n, i + n
}
if p < n*2+m {
return i + m, i - p + n*2 + m
}
return i - p + (n+m)*2, i
}

reverse := func(l, r int) {
for l < r {
x1, y1 := index(l)
x2, y2 := index(r)
grid[x1][y1], grid[x2][y2] = grid[x2][y2], grid[x1][y1]
l++
r--
}
}

// 189. 轮转数组（改成向左轮转）
size := (m + n) * 2
shift := k % size
reverse(0, shift-1)
reverse(shift, size-1)
reverse(0, size-1)
}

return grid
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

两种方法：正向 BFS / 逆向 BFS（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年7月27日 12:05

方法一：正向思维

整体是个 BFS 的框架。

设 $v=\textit{nums}[i]$。

如果 $v$ 不是质数，只能往 $i-1$ 和 $i+1$ 走一步。
如果 $v$ 是质数，除了能往 $i-1$ 和 $i+1$ 走一步，还能往 $v$ 在 $\textit{nums}$ 中的倍数那走一步。

怎么知道 $v$ 的倍数在哪？

预处理。在执行 BFS 之前，对于 $\textit{nums}$ 中的每个数 $x=\textit{nums}[i]$，把 $x$ 的的质因子 $p$ 和下标 $i$ 插入哈希表。哈希表的 key 是质数，value 是下标列表。

预处理后，从哈希表中可以直接获取到 $v$ 的倍数的下标。

注意遍历完下标列表后，要把列表从哈希表中删除（或者清空），避免反复遍历列表。比如一个有很多质数 $2$ 的数组，我们把这些 $2$ 的下标入队，出队的时候，不能重复遍历 $2$ 的倍数的下标列表。

代码实现时：

预处理每个数的质因子列表，思路和埃氏筛是一样的。
用双列表实现 BFS，原理请看【基础算法精讲 13】。当然，用队列也可以。

###py

# 预处理每个数的质因子列表，思路同埃氏筛
MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数有质因子 i
            prime_factors[j].append(i)

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            for p in prime_factors[x]:
                groups[p].append(i)  # 对于质数 p，可以跳到下标 i

        vis = [False] * n
        vis[0] = True
        q = [0]

        for ans in count(0):
            tmp = q
            q = []
            for i in tmp:
                if i == n - 1:
                    return ans
                idx = groups[nums[i]]
                idx.append(i + 1)
                if i:
                    idx.append(i - 1)
                for j in idx:  # 可以从 i 跳到 j
                    if not vis[j]:
                        vis[j] = True
                        q.append(j)
                idx.clear()  # 避免重复访问下标列表

###java

class Solution {
    private static final int MX = 1_000_001;
    private static final List<Integer>[] primeFactors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 更快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(primeFactors, _ -> new ArrayList<>());
        // 预处理每个数的质因子列表，思路同埃氏筛
        for (int i = 2; i < MX; i++) {
            if (primeFactors[i].isEmpty()) { // i 是质数
                for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                    primeFactors[j].add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int p : primeFactors[nums[i]]) {
                // 对于质数 p，可以跳到下标 i
                groups.computeIfAbsent(p, _ -> new ArrayList<>()).add(i);
            }
        }

        boolean[] vis = new boolean[n];
        vis[0] = true;
        List<Integer> q = List.of(0);

        for (int ans = 0; ; ans++) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                if (i == n - 1) {
                    return ans;
                }
                List<Integer> idx = groups.computeIfAbsent(nums[i], _ -> new ArrayList<>());
                idx.add(i + 1);
                if (i > 0) {
                    idx.add(i - 1);
                }
                for (int j : idx) { // 可以从 i 跳到 j
                    if (!vis[j]) {
                        vis[j] = true;
                        q.add(j);
                    }
                }
                idx.clear(); // 避免重复访问下标列表
            }
        }
    }
}

###cpp

const int MX = 1'000'001;
vector<int> prime_factors[MX];

int init = [] {
    // 预处理每个数的质因子列表，思路同埃氏筛
    for (int i = 2; i < MX; i++) {
        if (prime_factors[i].empty()) { // i 是质数
            for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                prime_factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            for (int p : prime_factors[nums[i]]) {
                groups[p].push_back(i); // 对于质数 p，可以跳到下标 i
            }
        }

        vector<int8_t> vis(n);
        vis[0] = true;
        vector<int> q = {0};

        for (int ans = 0; ; ans++) {
            auto tmp = q;
            q.clear();
            for (int i : tmp) {
                if (i == n - 1) {
                    return ans;
                }
                auto& idx = groups[nums[i]];
                idx.push_back(i + 1);
                if (i > 0) {
                    idx.push_back(i - 1);
                }
                for (int j : idx) { // 可以从 i 跳到 j
                    if (!vis[j]) {
                        vis[j] = true;
                        q.push_back(j);
                    }
                }
                idx.clear(); // 避免重复访问下标列表
            }
        }
    }
};

###go

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
// 预处理每个数的质因子列表，思路同埃氏筛
for i := 2; i < mx; i++ {
if primeFactors[i] == nil { // i 是质数
for j := i; j < mx; j += i { // i 的倍数有质因子 i
primeFactors[j] = append(primeFactors[j], i)
}
}
}
}

func minJumps(nums []int) (ans int) {
n := len(nums)
groups := map[int][]int{}
for i, x := range nums {
for _, p := range primeFactors[x] {
groups[p] = append(groups[p], i) // 对于质数 p，可以跳到下标 i
}
}

vis := make([]bool, n)
vis[0] = true
q := []int{0}

for ; ; ans++ {
tmp := q
q = nil
for _, i := range tmp {
if i == n-1 {
return
}
idx := groups[nums[i]]
idx = append(idx, i+1)
if i > 0 {
idx = append(idx, i-1)
}
for _, j := range idx { // 可以从 i 跳到 j
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
delete(groups, nums[i]) // 避免重复访问下标列表
}
}
}

复杂度分析

预处理的时间和空间不计入。

时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是 $\textit{nums}$ 的长度，$U=\max(\textit{nums})$。循环次数取决于下标列表的总长度（这决定了 BFS 的循环次数）。在最坏情况下，构造这样一个 $\textit{nums}$ 数组，它含有 $\mathcal{O}(\log U)$ 个不同的质数，以及 $\mathcal{O}(n-\log U)$ 个有 $\mathcal{O}(\log U)$ 个质因子的数。此时下标列表的总长度为 $\mathcal{O}(n\log U)$，且 BFS 的循环次数也为 $\mathcal{O}(n\log U)$。
空间复杂度：$\mathcal{O}(n\log U)$。

方法二：逆向思维

从终点 $n-1$ 跳到起点 $0$。

跳跃规则反过来，从 $i$ 跳到 $\textit{nums}[i]$ 的质因子 $p$ 的下标。

在执行 BFS 之前，对于 $\textit{nums}$ 中的每个数 $x=\textit{nums}[i]$，如果 $x$ 是质数，把 $x$ 和下标 $i$ 插入哈希表。哈希表的 key 是质数，value 是下标列表。

###py

# 预处理每个数的质因子列表，思路同埃氏筛
MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数有质因子 i
            prime_factors[j].append(i)

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            if prime_factors[x] and prime_factors[x][0] == x:  # x 是质数
                groups[x].append(i)

        ans = 0
        vis = [False] * n
        vis[-1] = True
        q = [n - 1]

        for ans in count(0):
            tmp = q
            q = []
            for i in tmp:
                if i == 0:
                    return ans
                if not vis[i - 1]:
                    vis[i - 1] = True
                    q.append(i - 1)
                if i < n - 1 and not vis[i + 1]:
                    vis[i + 1] = True
                    q.append(i + 1)
                # 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for p in prime_factors[nums[i]]:
                    idx = groups[p]
                    for j in idx:
                        if not vis[j]:
                            vis[j] = True
                            q.append(j)
                    idx.clear()  # 避免重复访问下标列表

###java

class Solution {
    private static final int MX = 1_000_001;
    private static final List<Integer>[] primeFactors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 更快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(primeFactors, _ -> new ArrayList<>());
        // 预处理每个数的质因子列表，思路同埃氏筛
        for (int i = 2; i < MX; i++) {
            if (primeFactors[i].isEmpty()) { // i 是质数
                for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                    primeFactors[j].add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (!primeFactors[x].isEmpty() && primeFactors[x].get(0) == x) { // x 是质数
                groups.computeIfAbsent(x, _ -> new ArrayList<>()).add(i);
            }
        }

        boolean[] vis = new boolean[n];
        vis[n - 1] = true;
        List<Integer> q = List.of(n - 1);

        for (int ans = 0; ; ans++) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                if (i == 0) {
                    return ans;
                }
                if (!vis[i - 1]) {
                    vis[i - 1] = true;
                    q.add(i - 1);
                }
                if (i + 1 < n && !vis[i + 1]) {
                    vis[i + 1] = true;
                    q.add(i + 1);
                }
                // 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for (int p : primeFactors[nums[i]]) {
                    List<Integer> idx = groups.remove(p); // 避免重复访问下标列表
                    if (idx != null) {
                        for (int j : idx) {
                            if (!vis[j]) {
                                vis[j] = true;
                                q.add(j);
                            }
                        }
                    }
                }
            }
        }
    }
}

###cpp

const int MX = 1'000'001;
vector<int> prime_factors[MX];

int init = [] {
    // 预处理每个数的质因子列表，思路同埃氏筛
    for (int i = 2; i < MX; i++) {
        if (prime_factors[i].empty()) { // i 是质数
            for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                prime_factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (!prime_factors[x].empty() && prime_factors[x][0] == x) { // x 是质数
                groups[x].push_back(i);
            }
        }

        vector<int8_t> vis(n);
        vis[n - 1] = true;
        vector<int> q = {n - 1};

        for (int ans = 0; ; ans++) {
            auto tmp = q;
            q.clear();
            for (int i : tmp) {
                if (i == 0) {
                    return ans;
                }
                if (!vis[i - 1]) {
                    vis[i - 1] = true;
                    q.push_back(i - 1);
                }
                if (i < n - 1 && !vis[i + 1]) {
                    vis[i + 1] = true;
                    q.push_back(i + 1);
                }
                // 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for (int p : prime_factors[nums[i]]) {
                    auto it = groups.find(p);
                    if (it != groups.end()) {
                        for (int j : it->second) {
                            if (!vis[j]) {
                                vis[j] = true;
                                q.push_back(j);
                            }
                        }
                        groups.erase(it); // 避免重复访问下标列表
                    }
                }
            }
        }
    }
};

###go

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
// 预处理每个数的质因子列表，思路同埃氏筛
for i := 2; i < mx; i++ {
if primeFactors[i] == nil { // i 是质数
for j := i; j < mx; j += i { // i 的倍数有质因子 i
primeFactors[j] = append(primeFactors[j], i)
}
}
}
}

func minJumps(nums []int) (ans int) {
n := len(nums)
groups := map[int][]int{}
for i, x := range nums {
if len(primeFactors[x]) > 0 && primeFactors[x][0] == x { // x 是质数
groups[x] = append(groups[x], i)
}
}

vis := make([]bool, n)
vis[n-1] = true
q := []int{n - 1}

for ; ; ans++ {
tmp := q
q = nil
for _, i := range tmp {
if i == 0 {
return
}
if !vis[i-1] {
vis[i-1] = true
q = append(q, i-1)
}
if i < n-1 && !vis[i+1] {
vis[i+1] = true
q = append(q, i+1)
}
// 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
for _, p := range primeFactors[nums[i]] {
for _, j := range groups[p] {
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
delete(groups, p) // 避免重复访问下标列表
}
}
}
}

复杂度分析

预处理的时间和空间不计入。

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

相似题目

1345. 跳跃游戏 IV 1810

分类题单

如何科学刷题？

我的题解精选（已分类）

结论 + 动态规划（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年8月24日 13:50

想一想，是 $\textit{ans}[0]$ 更好算，还是 $\textit{ans}[n-1]$ 更好算？

对于 $i=n-1$ 来说，它一定能跳到 $\textit{nums}$ 的最大值：

如果最大值等于 $\textit{nums}[n-1]$，那么命题成立。
否则最大值比 $\textit{nums}[n-1]$ 大，且下标小于 $n-1$。根据规则，能从 $n-1$ 跳到。

所以 $\textit{ans}[n-1] = \max(\textit{nums})$。

而对于 $\textit{ans}[0]$，就变得非常复杂了。比如 $\textit{nums}=[6,8,5,9,7]$，从 $6$ 跳到 $9$ 的顺序为 $6\to 5\to 8\to 7\to 9$。

所以倒着思考更简单。

那么，每个数都能跳到最大值吗？什么情况下无法跳到最大值？

比如 $\textit{nums}=[3,1,2,30,10,20]$，无法从 $3,1,2$ 跳到 $30,10,20$。在 $2$ 和 $30$ 之间有一条「分界线」，如果分界线左边的最大值比分界线右边的最小值还小（或者相等），那么无法从分界线左边跳到分界线右边，所以分界线左边的数无法跳到 $\textit{nums}$ 的最大值。

一般地，设 $[0,i]$ 中的最大值为 $\textit{preMax}[i]$，$[i+1,n-1]$ 中的最小值为 $\textit{sufMin}[i+1]$。

如果 $\textit{preMax}[i] \le \textit{sufMin}[i+1]$，对于 $[0,i]$ 中的任意下标 $p$ 和 $[i+1,n-1]$ 中的任意下标 $q$，我们有 $\textit{nums}[p]\le \textit{preMax}[i]\le \textit{sufMin}[i+1]\le \textit{nums}[q]$，所以 $[0,i]$ 中的任何下标都无法跳到 $[i+1,n-1]$ 中。问题变成 $[0,i]$ 的子问题。类似前文 $i=n-1$ 的讨论，我们有 $\textit{ans}[i] = \textit{preMax}[i]$。
否则 $\textit{preMax}[i] > \textit{sufMin}[i+1]$，我们可以先从 $i$ 跳到 $\textit{preMax}[i]$ 的位置，再跳到 $\textit{sufMin}[i+1]$ 的位置，最后跳到 $i+1$。所以 $i+1$ 能跳到的数，$i$ 也能跳到（反之亦然），所以 $\textit{ans}[i] = \textit{ans}[i+1]$。

一般地，我们有如下状态转移方程

$$
\textit{ans}[i] =
\begin{cases}
\textit{preMax}[i], & \textit{preMax}[i] \le \textit{sufMin}[i+1] \
\textit{ans}[i+1], & \textit{preMax}[i] > \textit{sufMin}[i+1] \
\end{cases}
$$

规定 $\textit{sufMin}[n] = \infty$。

代码实现时，可以在计算 $\textit{ans}$ 的同时计算 $\textit{sufMin}$，所以 $\textit{sufMin}$ 可以简化成一个变量。

###py

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = list(accumulate(nums, max))  # nums 的前缀最大值

        ans = [0] * n
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = pre_max[i] if pre_max[i] <= suf_min else ans[i + 1]
            suf_min = min(suf_min, nums[i])
        return ans

###py

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = [0] * n
        pre_max[0] = nums[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], nums[i])

        ans = [0] * n
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = pre_max[i] if pre_max[i] <= suf_min else ans[i + 1]
            suf_min = min(suf_min, nums[i])
        return ans

###java

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }

        int[] ans = new int[n];
        int sufMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = preMax[i] <= sufMin ? preMax[i] : ans[i + 1];
            sufMin = Math.min(sufMin, nums[i]);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre_max(n);
        pre_max[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], nums[i]);
        }

        vector<int> ans(n);
        int suf_min = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = pre_max[i] <= suf_min ? pre_max[i] : ans[i + 1];
            suf_min = min(suf_min, nums[i]);
        }
        return ans;
    }
};

###go

func maxValue(nums []int) []int {
n := len(nums)
preMax := make([]int, n)
preMax[0] = nums[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i-1], nums[i])
}

ans := make([]int, n)
sufMin := math.MaxInt
for i := n - 1; i >= 0; i-- {
if preMax[i] <= sufMin {
ans[i] = preMax[i]
} else {
ans[i] = ans[i+1]
}
sufMin = min(sufMin, nums[i])
}
return ans
}

也可以直接把答案保存在 $\textit{preMax}$ 中。

###py

# 手写 min max 更快
min = lambda a, b: b if b < a else a
max = lambda a, b: b if b > a else a

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = list(accumulate(nums, max))  # nums 的前缀最大值

        suf_min = inf
        for i in range(n - 1, -1, -1):
            if pre_max[i] > suf_min:
                pre_max[i] = pre_max[i + 1]
            suf_min = min(suf_min, nums[i])
        return pre_max

###java

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }

        int sufMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (preMax[i] > sufMin) {
                preMax[i] = preMax[i + 1];
            }
            sufMin = Math.min(sufMin, nums[i]);
        }
        return preMax;
    }
}

###cpp

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre_max(n);
        pre_max[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], nums[i]);
        }

        int suf_min = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            if (pre_max[i] > suf_min) {
                pre_max[i] = pre_max[i + 1];
            }
            suf_min = min(suf_min, nums[i]);
        }
        return pre_max;
    }
};

###go

func maxValue(nums []int) []int {
n := len(nums)
preMax := make([]int, n)
preMax[0] = nums[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i-1], nums[i])
}

sufMin := math.MaxInt
for i := n - 1; i >= 0; i-- {
if preMax[i] > sufMin {
preMax[i] = preMax[i+1]
}
sufMin = min(sufMin, nums[i])
}
return preMax
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

两种方法：正序遍历 / 倒序遍历（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2021年5月16日 00:56

方法一：正序遍历

$\textit{boxGrid}$ 的每一行互相独立，可以分别计算。

单独看每一行，我们需要知道每个障碍物（$\texttt{*}$）的左边有多少个石头（$\texttt{#}$）。

具体地，设当前障碍物到上一个障碍物之间有 $\textit{cnt}$ 个石头。那么旋转后，当前障碍物的左边有连续 $\textit{cnt}$ 个石头。据此：

在遍历过程中，统计石头的个数 $\textit{cnt}$。
如果下一个格子是障碍物，或者当前格子是最后一个格子，那么从当前格子往前填入连续 $\textit{cnt}$ 个石头，并重置计数器 $\textit{cnt}=0$。

细节：第 $i$ 行的格子旋转后在倒数第 $i$ 列，第 $j$ 列的格子旋转后在第 $j$ 行。所以 $(i,j)$ 旋转后位于 $(j,m-1-i)$。

class Solution:
    def rotateTheBox(self, boxGrid: list[list[str]]) -> list[list[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        ans = [[''] * m for _ in range(n)]

        for i, row in enumerate(boxGrid):
            cnt = 0
            for j, ch in enumerate(row):
                if ch == '#':  # 石头
                    cnt += 1
                    ch = '.'  # 先把石头清空
                ans[j][-1 - i] = ch
                if j == n - 1 or row[j + 1] == '*':  # 下一个格子是障碍物
                    # 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for k in range(j, j - cnt, -1):
                        ans[k][-1 - i] = '#'
                    cnt = 0  # 重置计数器

        return ans

class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        char[][] ans = new char[n][m];

        for (int i = 0; i < m; i++) {
            char[] row = boxGrid[i];
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                char ch = row[j];
                if (ch == '#') { // 石头
                    cnt++;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for (int k = j; k > j - cnt; k--) {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        return ans;
    }
}

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector ans(n, vector<char>(m));

        for (int i = 0; i < m; i++) {
            auto& row = boxGrid[i];
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                char ch = row[j];
                if (ch == '#') { // 石头
                    cnt++;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for (int k = j; k > j - cnt; k--) {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        return ans;
    }
};

char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) {
    int m = boxGridSize, n = boxGridColSize[0];
    char** ans = malloc(n * sizeof(char*));
    *returnColumnSizes = malloc(n * sizeof(int));
    *returnSize = n;
    for (int i = 0; i < n; i++) {
        ans[i] = malloc(m * sizeof(char));
        (*returnColumnSizes)[i] = m;
    }

    for (int i = 0; i < m; i++) {
        char* row = boxGrid[i];
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            char ch = row[j];
            if (ch == '#') { // 石头
                cnt++;
                ch = '.'; // 先把石头清空
            }
            ans[j][m - 1 - i] = ch;
            if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                for (int k = j; k > j - cnt; k--) {
                    ans[k][m - 1 - i] = '#';
                }
                cnt = 0; // 重置计数器
            }
        }
    }

    return ans;
}

func rotateTheBox(boxGrid [][]byte) [][]byte {
m, n := len(boxGrid), len(boxGrid[0])
ans := make([][]byte, n)
for i := range ans {
ans[i] = make([]byte, m)
}

for i, row := range boxGrid {
cnt := 0
for j, ch := range row {
if ch == '#' { // 石头
cnt++
ch = '.' // 先把石头清空
}
ans[j][m-1-i] = ch
if j == n-1 || row[j+1] == '*' { // 下一个格子是障碍物
// 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
for k := j; k > j-cnt; k-- {
ans[k][m-1-i] = '#'
}
cnt = 0 // 重置计数器
}
}
}

return ans
}

var rotateTheBox = function(boxGrid) {
    const m = boxGrid.length, n = boxGrid[0].length;
    const ans = Array.from({ length: n }, () => Array(m));

    for (let i = 0; i < m; i++) {
        const row = boxGrid[i];
        let cnt = 0;
        for (let j = 0; j < n; j++) {
            let ch = row[j];
            if (ch === '#') { // 石头
                cnt++;
                ch = '.'; // 先把石头清空
            }
            ans[j][m - 1 - i] = ch;
            if (j === n - 1 || row[j + 1] === '*') { // 下一个格子是障碍物
                // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                for (let k = j; k > j - cnt; k--) {
                    ans[k][m - 1 - i] = '#';
                }
                cnt = 0; // 重置计数器
            }
        }
    }

    return ans;
};

impl Solution {
    pub fn rotate_the_box(box_grid: Vec<Vec<char>>) -> Vec<Vec<char>> {
        let m = box_grid.len();
        let n = box_grid[0].len();
        let mut ans = vec![vec!['\0'; m]; n];

        for (i, row) in box_grid.iter().enumerate() {
            let mut cnt = 0;
            for (j, &ch) in row.into_iter().enumerate() {
                let mut ch = ch;
                if ch == '#' { // 石头
                    cnt += 1;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if j == n - 1 || row[j + 1] == '*' { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for k in j - cnt + 1..=j {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{boxGrid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

方法二：倒序遍历 + 双指针

对于每一行 $\textit{row}$，倒着遍历，我们可以直接确定每个石头落入的位置：

如果 $\textit{row}[j]$ 是障碍物，那么它左边最近的石头，在旋转后掉落到 $\textit{row}[j-1]$。我们用一个变量 $k$ 维护石头掉落后的位置，如果 $\textit{row}[j]$ 是障碍物，那么更新 $\textit{k} = j-1$。注：如果 $\textit{row}[j]$ 左边最近的不是石头而是障碍物，那么 $k$ 会继续更新，无需担心石头落到错误的位置。
如果 $\textit{row}[j]$ 是石头，那么它掉落到 $\textit{row}[\textit{k}]$。然后把 $k$ 减一，表示左边下一块石头掉落后的位置。

class Solution:
    def rotateTheBox(self, boxGrid: list[list[str]]) -> list[list[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        ans = [['.'] * m for _ in range(n)]

        for i, row in enumerate(boxGrid):
            k = n - 1
            for j in range(n - 1, -1, -1):
                if row[j] == '*':  # 障碍物
                    ans[j][-1 - i] = '*'
                    k = j - 1  # 障碍物左边最近的石头，在旋转后掉落到 j-1
                elif row[j] == '#':  # 石头
                    ans[k][-1 - i] = '#'  # 旋转后，石头掉落到 k
                    k -= 1

        return ans

class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        char[][] ans = new char[n][m];
        for (char[] row : ans) {
            Arrays.fill(row, '.');
        }

        for (int i = 0; i < m; i++) {
            char[] row = boxGrid[i];
            int k = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (row[j] == '*') { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if (row[j] == '#') { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k--;
                }
            }
        }

        return ans;
    }
}

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector ans(n, vector<char>(m, '.'));

        for (int i = 0; i < m; i++) {
            auto& row = boxGrid[i];
            int k = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (row[j] == '*') { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if (row[j] == '#') { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k--;
                }
            }
        }

        return ans;
    }
};

char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) {
    int m = boxGridSize, n = boxGridColSize[0];
    char** ans = malloc(n * sizeof(char*));
    *returnColumnSizes = malloc(n * sizeof(int));
    *returnSize = n;
    for (int i = 0; i < n; i++) {
        ans[i] = malloc(m * sizeof(char));
        memset(ans[i], '.', m * sizeof(char));
        (*returnColumnSizes)[i] = m;
    }

    for (int i = 0; i < m; i++) {
        char* row = boxGrid[i];
        int k = n - 1;
        for (int j = n - 1; j >= 0; j--) {
            if (row[j] == '*') { // 障碍物
                ans[j][m - 1 - i] = '*';
                k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
            } else if (row[j] == '#') { // 石头
                ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                k--;
            }
        }
    }

    return ans;
}

func rotateTheBox(boxGrid [][]byte) [][]byte {
m, n := len(boxGrid), len(boxGrid[0])
ans := make([][]byte, n)
for i := range ans {
ans[i] = bytes.Repeat([]byte{'.'}, m)
}

for i, row := range boxGrid {
k := n - 1
for j := n - 1; j >= 0; j-- {
if row[j] == '*' { // 障碍物
ans[j][m-1-i] = '*'
k = j - 1 // 障碍物左边最近的石头，在旋转后掉落到 j-1
} else if row[j] == '#' { // 石头
ans[k][m-1-i] = '#' // 旋转后，石头掉落到 k
k--
}
}
}

return ans
}

var rotateTheBox = function(boxGrid) {
    const m = boxGrid.length, n = boxGrid[0].length;
    const ans = Array.from({ length: n }, () => Array(m).fill('.'));

    for (let i = 0; i < m; i++) {
        const row = boxGrid[i];
        let k = n - 1;
        for (let j = n - 1; j >= 0; j--) {
            if (row[j] === '*') { // 障碍物
                ans[j][m - 1 - i] = '*';
                k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
            } else if (row[j] === '#') { // 石头
                ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                k--;
            }
        }
    }

    return ans;
};

impl Solution {
    pub fn rotate_the_box(box_grid: Vec<Vec<char>>) -> Vec<Vec<char>> {
        let m = box_grid.len();
        let n = box_grid[0].len();
        let mut ans = vec![vec!['.'; m]; n];

        for (i, row) in box_grid.into_iter().enumerate() {
            let mut k = n - 1;
            for (j, ch) in row.into_iter().enumerate().rev() {
                if ch == '*' { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if ch == '#' { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k -= 1;
                }
            }
        }

        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{boxGrid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

专题训练

见下面双指针题单的「六、分组循环」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

首尾相连再断开（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2026年5月4日 09:30

示例 1 的链表长为 $5$，$k=2$。旋转后，原链表的倒数第 $k$ 个节点，成为新链表的头节点。

把 $1\to 2\to 3\to 4\to 5$ 变成 $4\to 5\to 1\to 2\to 3$，我们需要：

首尾相连，把 $5$ 和 $1$ 连起来。遍历链表即可找到尾节点。
断开倒数第 $k+1$ 个节点和倒数第 $k$ 个节点，即断开 $3\to 4$。

本题 $k$ 可能很大，我们需要先求出链表的长度 $n$，然后把 $k$ 更新为 $k\bmod n$。这是因为链表旋转 $n$ 次没变，旋转 $n+1$ 次等同于旋转 $1$ 次，依此类推，旋转 $k$ 次等价于旋转 $k\bmod n$ 次。

倒数第 $k+1$ 个节点即正数第 $n-k$ 个节点。从头节点开始，向后移动 $n-k-1$ 次，即为正数第 $n-k$ 个节点。

###py

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None:
            return None

        # 1. 计算链表长度，并找到尾节点
        length = 1
        tail = head
        while tail.next:
            length += 1
            tail = tail.next
        k %= length

        # 2. 首尾相连
        tail.next = head

        # 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        new_tail = head
        for _ in range(length - k - 1):
            new_tail = new_tail.next

        # 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
        new_head = new_tail.next
        new_tail.next = None
        return new_head

###java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        // 1. 计算链表长度，并找到尾节点
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            length++;
            tail = tail.next;
        }
        k %= length;

        // 2. 首尾相连
        tail.next = head;

        // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        ListNode newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail.next;
        }

        // 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

###cpp

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr) {
            return nullptr;
        }

        // 1. 计算链表长度，并找到尾节点
        int length = 1;
        ListNode* tail = head;
        while (tail->next) {
            length++;
            tail = tail->next;
        }
        k %= length;

        // 2. 首尾相连
        tail->next = head;

        // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        ListNode* new_tail = head;
        for (int i = 0; i < length - k - 1; i++) {
            new_tail = new_tail->next;
        }

        // 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
        ListNode* new_head = new_tail->next;
        new_tail->next = nullptr;
        return new_head;
    }
};

###c

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (head == NULL) {
        return NULL;
    }

    // 1. 计算链表长度，并找到尾节点
    int length = 1;
    struct ListNode* tail = head;
    while (tail->next) {
        length++;
        tail = tail->next;
    }
    k %= length;

    // 2. 首尾相连
    tail->next = head;

    // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
    struct ListNode* new_tail = head;
    for (int i = 0; i < length - k - 1; i++) {
        new_tail = new_tail->next;
    }

    // 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
    struct ListNode* new_head = new_tail->next;
    new_tail->next = NULL;
    return new_head;
}

###go

func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return nil
}

// 1. 计算链表长度，并找到尾节点
length := 1
tail := head
for tail.Next != nil {
length++
tail = tail.Next
}
k %= length

// 2. 首尾相连
tail.Next = head

// 3. 找倒数第 k+1 个节点，作为新链表的尾节点
newTail := head
for range length - k - 1 {
newTail = newTail.Next
}

// 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
newHead := newTail.Next
newTail.Next = nil
return newHead
}

###js

var rotateRight = function(head, k) {
    if (head === null) {
        return null;
    }

    // 1. 计算链表长度，并找到尾节点
    let length = 1;
    let tail = head;
    while (tail.next !== null) {
        length++;
        tail = tail.next;
    }
    k %= length;

    // 2. 首尾相连
    tail.next = head;

    // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
    let newTail = head;
    for (let i = 0; i < length - k - 1; i++) {
        newTail = newTail.next;
    }

    // 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
    const newHead = newTail.next;
    newTail.next = null;
    return newHead;
};

###rust

impl Solution {
    pub fn rotate_right(mut head: Option<Box<ListNode>>, mut k: i32) -> Option<Box<ListNode>> {
        if head.is_none() {
            return head;
        }

        // 1. 计算链表长度
        let mut length = 0;
        let mut cur = &head;
        while let Some(node) = cur {
            length += 1;
            cur = &node.next;
        }

        k %= length;
        if k == 0 { // 链表不变
            return head;
        }

        // 2. 找倒数第 k 个节点
        let mut cur = &mut head;
        for _ in 0..length - k {
            cur = &mut cur.as_mut()?.next;
        }

        // 3. 断开倒数第 k+1 个节点和倒数第 k 个节点（new_head）
        let mut new_head = cur.take();

        // 4. 首尾相连
        let mut tail = &mut new_head;
        while !tail.as_mut()?.next.is_none() {
            tail = &mut tail.as_mut()?.next;
        }
        tail.as_mut()?.next = head;

        new_head
    }
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

数学本质：两次翻转等于一次旋转（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2025年4月18日 16:34

题意

把一个方阵（$n\times n$ 的矩阵）顺时针旋转 $90^\circ$。

要求：不能创建另一个矩阵，空间复杂度必须是 $\mathcal{O}(1)$。

分析

顺时针旋转 $90^\circ$ 后，位于 $(i,j)$ 的元素去哪了？

竖着看：

第一列的元素去到第一行。
第二列的元素去到第二行。
……
第 $j$ 列的元素去到第 $j$ 行。

横着看：

第一行的元素去到最后一列。
第二行的元素去到倒数第二列。
……
第 $i$ 行的元素去到第 $n-1-i$ 列。（$i$ 从 $0$ 开始）

所以位于 $i$ 行 $j$ 列的元素，去到 $j$ 行 $n-1-i$ 列，即 $(i,j)\to (j,n-1-i)$。

两次翻转等于一次旋转

$(i,j)\to (j,n-1-i)$ 可以通过两次翻转操作得到：

$$
(i,j)\xrightarrow{转置} (j,i) \xrightarrow{行翻转} (j,n-1-i)
$$

转置：把矩阵按照主对角线翻转，位于 $(i,j)$ 的元素去到 $(j,i)$。
行翻转：把每一行翻转，位于 $(j,i)$ 的元素去到 $(j,n-1-i)$。

示例 1 的操作过程如下：

$$
\begin{bmatrix}
1 & 2 & 3 \
4 & 5 & 6 \
7 & 8 & 9 \
\end{bmatrix}
\xrightarrow{转置}
\begin{bmatrix}
1 & 4 & 7 \
2 & 5 & 8 \
3 & 6 & 9 \
\end{bmatrix}
\xrightarrow{行翻转}
\begin{bmatrix}
7 & 4 & 1 \
8 & 5 & 2 \
9 & 6 & 3 \
\end{bmatrix}
$$

注：一般地，把一个点绕 $O$ 旋转任意 $\theta$ 角度，可以通过两个翻转操作实现。要求这两条翻转的对称轴，交点为 $O$ 且夹角为 $\dfrac{\theta}{2}$。对于本题，每个元素需要绕矩阵中心顺时针旋转 $90^\circ$，这可以通过关于主对角线翻转，关于垂直中轴翻转实现。这两条对称轴的交点为矩阵中心，且夹角为 $45^\circ$。

实现

转置：把主对角线下面的元素 $\textit{matrix}[i][j]$ 和（关于主对角线）对称位置的元素 $\textit{matrix}[j][i]$ 交换。
行翻转：遍历每一行 $\textit{row}=\textit{matrix}[i]$，把左半边的元素 $\textit{row}[j]$ 和（关于垂直中轴）对称位置的元素 $\textit{row}[n-1-j]$ 交换。或者，使用库函数翻转 $\textit{row}$。

这两步操作都可以原地实现。

写法一

###py

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 第一步：转置
        for i in range(n):
            for j in range(i):  # 遍历对角线下方元素
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 第二步：行翻转
        for row in matrix:
            row.reverse()

###java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 第一步：转置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) { // 遍历对角线下方元素
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }

        // 第二步：行翻转
        for (int[] row : matrix) {
            for (int j = 0; j < n / 2; j++) { // 遍历左半元素
                int tmp = row[j];
                row[j] = row[n - 1 - j];
                row[n - 1 - j] = tmp;
            }
        }
    }
}

###cpp

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 第一步：转置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) { // 遍历对角线下方元素
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 第二步：行翻转
        for (auto& row : matrix) {
            ranges::reverse(row);
        }
    }
};

###c

#define SWAP(a, b) do { int tmp = (a); (a) = (b); (b) = tmp; } while (0)

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;
    // 第一步：转置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) { // 遍历对角线下方元素
            SWAP(matrix[i][j], matrix[j][i]);
        }
    }

    // 第二步：行翻转
    for (int i = 0; i < n; i++) {
        int* row = matrix[i];
        for (int j = 0; j < n / 2; j++) { // 遍历左半元素
            SWAP(row[j], row[n - 1 - j]);
        }
    }
}

###go

func rotate(matrix [][]int) {
    n := len(matrix)
    // 第一步：转置
    for i := range n {
        for j := range i { // 遍历对角线下方元素
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }

    // 第二步：行翻转
    for _, row := range matrix {
        slices.Reverse(row)
    }
}

###js

var rotate = function(matrix) {
    const n = matrix.length;
    // 第一步：转置
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) { // 遍历对角线下方元素
            const tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }

    // 第二步：行翻转
    for (const row of matrix) {
        row.reverse();
    }
};

###rust

impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();
        // 第一步：转置
        for i in 0..n {
            for j in 0..i { // 遍历对角线下方元素
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
            }
        }

        // 第二步：行翻转
        for row in matrix {
            row.reverse();
        }
    }
}

写法二

把两个循环合并成一个循环。

需要把遍历顺序调整为遍历对角线上方元素，这样每行遍历完后，这一行的元素后面不会再访问到，可以直接做行翻转。

###py

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i, row in enumerate(matrix):
            for j in range(i + 1, n):  # 遍历对角线上方元素，做转置
                row[j], matrix[j][i] = matrix[j][i], row[j]
            row.reverse()  # 行翻转

###java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            int[] row = matrix[i];
            for (int j = i + 1; j < n; j++) { // 遍历对角线上方元素，做转置
                int tmp = row[j];
                row[j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
            for (int j = 0; j < n / 2; j++) { // 遍历左半元素，做行翻转
                int tmp = row[j];
                row[j] = row[n - 1 - j];
                row[n - 1 - j] = tmp;
            }
        }
    }
}

###cpp

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // 遍历对角线上方元素，做转置
                swap(matrix[i][j], matrix[j][i]);
            }
            ranges::reverse(matrix[i]); // 行翻转
        }
    }
};

###c

#define SWAP(a, b) do { int tmp = (a); (a) = (b); (b) = tmp; } while (0)

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;
    for (int i = 0; i < n; i++) {
        int* row = matrix[i];
        for (int j = i + 1; j < n; j++) { // 遍历对角线上方元素，做转置
            SWAP(row[j], matrix[j][i]);
        }
        for (int j = 0; j < n / 2; j++) { // 遍历左半元素，做行翻转
            SWAP(row[j], row[n - 1 - j]);
        }
    }
}

###go

func rotate(matrix [][]int) {
    n := len(matrix)
    for i, row := range matrix {
        for j := i + 1; j < n; j++ { // 遍历对角线上方元素，做转置
            row[j], matrix[j][i] = matrix[j][i], row[j]
        }
        slices.Reverse(row) // 行翻转
    }
}

###js

var rotate = function(matrix) {
    const n = matrix.length;
    for (let i = 0; i < n; i++) {
        const row = matrix[i];
        for (let j = i + 1; j < n; j++) { // 遍历对角线上方元素，做转置
            const tmp = row[j];
            row[j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
        row.reverse(); // 行翻转
    }
};

###rust

impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();
        for i in 0..n {
            for j in i + 1..n { // 遍历对角线上方元素，做转置
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
            }
            matrix[i].reverse(); // 行翻转
        }
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $\textit{matrix}$ 的行数和列数。
空间复杂度：$\mathcal{O}(1)$。

思考题

改成顺时针旋转 $180^\circ$，要怎么做？
改成顺时针旋转 $270^\circ$（逆时针旋转 $90^\circ$），要怎么做？

欢迎在评论区分享你的思路/代码。

相似题目

189. 轮转数组

分类题单

如何科学刷题？

我的题解精选（已分类）

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

两种方法：暴力 / KMP（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2026年5月2日 15:10

方法一：暴力

例如 $s=\texttt{abcde}$，旋转一次变成 $\texttt{bcdea}$，再旋转一次变成 $\texttt{cdeab}$。旋转后的字符串是 $s$ 的后缀加上 $s$ 的前缀，例如 $\texttt{cdeab} = \texttt{cde} + \texttt{ab}$。于是构造 $s+s = \texttt{abcdeabcde}$，这个字符串的任意长为 $n$ 的子串，都是 $s$ 的后缀加上 $s$ 的前缀。所以无论 $s$ 如何旋转，旋转后的字符串一定是 $s+s$ 的子串。

于是问题等价于：

判断 $s+s$ 是否包含 $\textit{goal}$。

注意题目没有保证 $s$ 和 $\textit{goal}$ 长度相等，如果不等，直接返回 $\texttt{false}$。

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && (s + s).contains(goal);
    }
};

func rotateString(s, goal string) bool {
return len(s) == len(goal) && strings.Contains(s+s, goal)
}

复杂度分析

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

方法二：字符串匹配

用 KMP、Z 函数、字符串哈希等算法，都可以 $\mathcal{O}(n)$ 判断 $s+s$ 是否包含 $\textit{goal}$。

下面用的 KMP 算法，原理见 KMP 算法讲解。

# 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
# 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
def kmp_search(text: str, pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    cnt = 0
    for i in range(1, m):
        b = pattern[i]
        while cnt and pattern[cnt] != b:
            cnt = pi[cnt - 1]
        if pattern[cnt] == b:
            cnt += 1
        pi[i] = cnt

    pos = []
    cnt = 0
    for i, b in enumerate(text):
        while cnt and pattern[cnt] != b:
            cnt = pi[cnt - 1]
        if pattern[cnt] == b:
            cnt += 1
        if cnt == len(pattern):
            pos.append(i - m + 1)
            cnt = pi[cnt - 1]
    return pos

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and len(kmp_search(s + s, goal)) > 0

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && 
               !kmpSearch((s + s).toCharArray(), goal.toCharArray()).isEmpty();
    }

    // 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
    // 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
    private List<Integer> kmpSearch(char[] text, char[] pattern) {
        int m = pattern.length;
        int[] pi = new int[m];
        int cnt = 0;
        for (int i = 1; i < m; i++) {
            char b = pattern[i];
            while (cnt > 0 && pattern[cnt] != b) {
                cnt = pi[cnt - 1];
            }
            if (pattern[cnt] == b) {
                cnt++;
            }
            pi[i] = cnt;
        }

        List<Integer> pos = new ArrayList<>();
        cnt = 0;
        for (int i = 0; i < text.length; i++) {
            char b = text[i];
            while (cnt > 0 && pattern[cnt] != b) {
                cnt = pi[cnt - 1];
            }
            if (pattern[cnt] == b) {
                cnt++;
            }
            if (cnt == m) {
                pos.add(i - m + 1);
                cnt = pi[cnt - 1];
            }
        }
        return pos;
    }
}

class Solution {
    // 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
    // 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
    vector<int> kmp_search(const string& text, const string& pattern) {
        int m = pattern.size();
        vector<int> pi(m);
        int cnt = 0;
        for (int i = 1; i < m; i++) {
            char b = pattern[i];
            while (cnt && pattern[cnt] != b) {
                cnt = pi[cnt - 1];
            }
            if (pattern[cnt] == b) {
                cnt++;
            }
            pi[i] = cnt;
        }
    
        vector<int> pos;
        cnt = 0;
        for (int i = 0; i < text.size(); i++) {
            char b = text[i];
            while (cnt && pattern[cnt] != b) {
                cnt = pi[cnt - 1];
            }
            if (pattern[cnt] == b) {
                cnt++;
            }
            if (cnt == m) {
                pos.push_back(i - m + 1);
                cnt = pi[cnt - 1];
            }
        }
        return pos;
    }

public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && !kmp_search(s + s, goal).empty();
    }
};

// 下面是 KMP 模板。对于本题来说，找到一个就可以返回了。为方便大家使用，我保留了完整的模板。
// 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
func kmpSearch(text, pattern string) (pos []int) {
m := len(pattern)
pi := make([]int, m)
cnt := 0
for i := 1; i < m; i++ {
b := pattern[i]
for cnt > 0 && pattern[cnt] != b {
cnt = pi[cnt-1]
}
if pattern[cnt] == b {
cnt++
}
pi[i] = cnt
}

cnt = 0
for i, b := range text {
for cnt > 0 && pattern[cnt] != byte(b) {
cnt = pi[cnt-1]
}
if pattern[cnt] == byte(b) {
cnt++
}
if cnt == m {
pos = append(pos, i-m+1)
cnt = pi[cnt-1]
}
}
return
}

func rotateString(s, goal string) bool {
return len(s) == len(goal) && kmpSearch(s+s, goal) != nil
}

复杂度分析

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

专题训练

见下面字符串题单的「一、KMP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

数位 DP 通用模板（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2022年9月25日 08:29

视频讲解，从 19:30 开始（基于题目 2376. 统计特殊整数）。
讲了数位 DP 的通用模板，以及如何使用该模板秒杀相关困难题目。
讲完题目后还讲了一些上分的训练技巧。

根据题意，好数中不能有 $3,4,7$，且至少包含 $2,5,6,9$ 中的一个。

将 $n$ 转换成字符串 $s$，定义 $f(i,\textit{hasDiff}, \textit{isLimit}, \textit{isNum})$ 表示构造从左往右第 $i$ 位及其之后数位的合法方案数，其余参数的含义为：

$\textit{hasDiff}$ 表示前面填的数字是否包含 $2,5,6,9$（至少一个）。
$\textit{isLimit}$ 表示当前是否受到了 $n$ 的约束。若为真，则第 $i$ 位填入的数字至多为 $s[i]$，否则可以是 $9$。如果在受到约束的情况下填了 $s[i]$，那么后续填入的数字仍会受到 $n$ 的约束。
$\textit{isNum}$ 表示 $i$ 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 $1$；若为真，则要填入的数字可以从 $0$ 开始。

后面两个参数可适用于其它数位 DP 题目。

枚举要填入的数字，具体实现逻辑见代码。对于本题来说，由于前导零对答案无影响，$\textit{isNum}$ 可以省略。

下面代码中 Java/C++/Go 只需要记忆化 $(i,\textit{hasDiff})$ 这个状态，因为：

对于一个固定的 $(i,\textit{hasDiff})$，这个状态受到 $\textit{isLimit}$ 的约束在整个递归过程中至多会出现一次，没必要记忆化。比如 $n=1234$，当 $i=2$ 的时候，前面可以填 $10,11,12$ 等等，如果受到 $\textit{isLimit}$ 的约束，就说明前面填的是 $12$。「当 $i=2$ 的时候，前面填的是 $12$」这件事情，在整个递归中只会发生一次。
另外，如果只记忆化 $(i,\textit{hasDiff})$，$\textit{dp}$ 数组的含义就变成在不受到约束时的合法方案数，所以要在 !isLimit 成立时才去记忆化。接着上面的例子，在前面填 $12$ 的时候，下一位填的数字不能超过 $3$，因此算出来的结果是不能套用到前面填的是 $10,11$ 这些数字上面的。

DIFFS = (0, 0, 1, -1, -1, 1, 1, -1, 0, 1)

class Solution:
    def rotatedDigits(self, n: int) -> int:
        s = str(n)
        @cache
        def f(i: int, has_diff: bool, is_limit: bool) -> int:
            if i == len(s):
                return has_diff  # 只有包含 2/5/6/9 才算一个好数
            res = 0
            up = int(s[i]) if is_limit else 9
            for d in range(0, up + 1):  # 枚举要填入的数字 d
                if DIFFS[d] != -1:  # d 不是 3/4/7
                    res += f(i + 1, has_diff or DIFFS[d], is_limit and d == up)
            return res
        return f(0, False, True)

class Solution {
    private static int[] DIFFS = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

    public int rotatedDigits(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int[][] memo = new int[s.length][2];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(0, 0, true, s, memo);
    }

    private int dfs(int i, int hasDiff, boolean isLimit, char[] s, int[][] memo) {
        if (i == s.length) {
            return hasDiff; // 只有包含 2/5/6/9 才算一个好数
        }
        if (!isLimit && memo[i][hasDiff] >= 0) {
            return memo[i][hasDiff];
        }
        int res = 0;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
            if (DIFFS[d] != -1) { // d 不是 3/4/7
                res += dfs(i + 1, hasDiff | DIFFS[d], isLimit && d == up, s, memo);
            }
        }
        if (!isLimit) {
            memo[i][hasDiff] = res;
        }
        return res;
    }
}

int diffs[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

class Solution {
public:
    int rotatedDigits(int n) {
        string s = to_string(n);
        int m = s.size();
        vector<array<int, 2>> memo(m, {-1, -1});

        auto dfs = [&](this auto&& dfs, int i, bool has_diff, bool is_limit) -> int {
            if (i == m) {
                return has_diff; // 只有包含 2/5/6/9 才算一个好数
            }
            if (!is_limit && memo[i][has_diff] >= 0) {
                return memo[i][has_diff];
            }
            int res = 0;
            int up = is_limit ? s[i] - '0' : 9;
            for (int d = 0; d <= up; d++) { // 枚举要填入的数字 d
                if (diffs[d] != -1) { // d 不是 3/4/7
                    res += dfs(i + 1, has_diff || diffs[d], is_limit && d == up);
                }
            }
            if (!is_limit) {
                memo[i][has_diff] = res;
            }
            return res;
        };

        return dfs(0, false, true);
    }
};

var diffs = [10]int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1}

func rotatedDigits(n int) int {
s := strconv.Itoa(n)
m := len(s)
memo := make([][2]int, m)
for i := range memo {
memo[i] = [2]int{-1, -1}
}
var dfs func(int, int, bool) int
dfs = func(i, isDiff int, isLimit bool) (res int) {
if i == m {
return isDiff // 只有包含 2/5/6/9 才算一个好数
}
if !isLimit {
p := &memo[i][isDiff]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
up := 9
if isLimit {
up = int(s[i] - '0')
}
for d := 0; d <= up; d++ { // 枚举要填入的数字 d
if diffs[d] != -1 { // d 不是 3/4/7
res += dfs(i+1, isDiff|diffs[d], isLimit && d == up)
}
}
return
}
return dfs(0, 0, true)
}

复杂度分析

时间复杂度：$\mathcal{O}(mD)$，其中 $m=\mathcal{O}(\log n),\ D=10$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(m)$，单个状态的计算时间为 $\mathcal{O}(D)$，所以动态规划的时间复杂度为 $\mathcal{O}(mD)$。
空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「十、数位 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

增量法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2026年5月1日 06:34

为方便描述，本文把 $\textit{nums}$ 简称为 $a$。

如果分别计算 $F(0),F(1),\ldots,F(n-1)$，总的时间复杂度是 $\mathcal{O}(n^2)$，太慢了。

考察相邻两项的差值，能否加快计算过程？

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2)
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3)
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4)

从 $F(0)$ 到 $F(1)$，$a_0,a_1,a_2,a_3$ 的系数是怎么变的？

$a_0,a_1,a_2$ 往右移动一位，系数都增加了 $1$。
$a_3$ 移到了最前面，系数减少了 $n-1=3$。

所以 $F(1) = F(0) + a_0+a_1+a_2-3a_3 = F(0) + (a_0+a_1+a_2+a_3)-4a_3$。

这意味着，如果已知 $F(0)$ 以及 $a$ 的总和 $S$，就可以 $\mathcal{O}(1)$ 算出

$$
F(1) = F(0) + S - n\cdot a_{n-1}
$$

从 $F(1)$ 到 $F(2)$，$a_0,a_1,a_2,a_3$ 的系数是怎么变的？

$a_3,a_0,a_1$ 往右移动一位，系数都增加了 $1$。
$a_2$ 移到了最前面，系数减少了 $n-1=3$。
相当于把每个数的系数都增加 $1$，然后把 $a_2$（原数组的倒数第二项）的系数减少 $n=4$。

所以有

$$
F(2) = F(1) + S - n\cdot a_{n-2}
$$

一般地，从 $F(i-1)$ 到 $F(i)$：

除了 $a_{n-i}$，其余每个数都往右移动一位，系数都增加了 $1$。
$a_{n-i}$ 移到了最前面，系数减少了 $n-1$。
相当于把每个数的系数都增加 $1$，然后把 $a_{n-i}$ 的系数减少 $n$。

所以有

$$
F(i) = F(i-1) + S - n\cdot a_{n-i}
$$

根据上式，我们可以先算出 $F(0)$，然后从 $F(0)$ 开始，递推算出 $F(1),F(2),\ldots,F(n-1)$。

答案为所有 $F(i)$ 的最大值。

class Solution:
    def maxRotateFunction(self, nums: list[int]) -> int:
        n = len(nums)
        f = sum(i * x for i, x in enumerate(nums))  # F(0)
        s = sum(nums)  # nums 的总和

        ans = f
        for i in range(n - 1, 0, -1):
            f += s - n * nums[i]
            ans = max(ans, f)
        return ans

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int f = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            f += i * nums[i]; // 计算 F(0)
            sum += nums[i]; // 计算 nums 的总和
        }

        int ans = f;
        for (int i = n - 1; i > 0; i--) {
            f += sum - n * nums[i];
            ans = Math.max(ans, f);
        }
        return ans;
    }
}

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        int f = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            f += i * nums[i]; // 计算 F(0)
            sum += nums[i]; // 计算 nums 的总和
        }

        int ans = f;
        for (int i = n - 1; i > 0; i--) {
            f += sum - n * nums[i];
            ans = max(ans, f);
        }
        return ans;
    }
};

int maxRotateFunction(int* nums, int numsSize) {
    int f = 0;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        f += i * nums[i]; // 计算 F(0)
        sum += nums[i]; // 计算 nums 的总和
    }

    int ans = f;
    for (int i = numsSize - 1; i > 0; i--) {
        f += sum - numsSize * nums[i];
        ans = MAX(ans, f);
    }
    return ans;
}

func maxRotateFunction(nums []int) int {
n := len(nums)
f := 0
sum := 0
for i, x := range nums {
f += i * x // 计算 F(0)
sum += x // 计算 nums 的总和
}

ans := f
for i := n - 1; i > 0; i-- {
f += sum - n*nums[i]
ans = max(ans, f)
}
return ans
}

var maxRotateFunction = function(nums) {
    const n = nums.length;
    let f = 0;
    let sum = 0;
    for (let i = 0; i < n; i++) {
        f += i * nums[i]; // 计算 F(0)
        sum += nums[i]; // 计算 nums 的总和
    }

    let ans = f;
    for (let i = n - 1; i > 0; i--) {
        f += sum - n * nums[i];
        ans = Math.max(ans, f);
    }
    return ans;
};

impl Solution {
    pub fn max_rotate_function(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut f = 0;
        let mut sum = 0;
        for (i, &x) in nums.iter().enumerate() {
            f += i as i32 * x; // 计算 F(0)
            sum += x; // 计算 nums 的总和
        }

        let mut ans = f;
        for i in (1..n).rev() {
            f += sum - n as i32 * nums[i];
            ans = ans.max(f);
        }
        ans
    }
}

复杂度分析

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

相似题目

2121. 相同元素的间隔之和

分类题单

如何科学刷题？

我的题解精选（已分类）

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

网格图 DP + 优化循环次数（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年11月9日 12:24

做法类似 3418. 机器人可以获得的最大金币数，我的题解。

和 3418 题一样，定义 $\textit{dfs}(i,j,k)$ 表示从 $(0,0)$ 走到 $(i,j)$，在总花费不超过 $k$ 的情况下，可以获得的最大分数。

设 $x = \textit{grid}[i][j]$。
首先，如果 $x>0$，把 $k$ 减少一。设新的 $k$ 为 $k'$。
如果最后一步从 $(i-1,j)$ 走到 $(i,j)$，那么问题变成从 $(0,0)$ 走到 $(i-1,j)$，在总花费不超过 $k'$ 的情况下，可以获得的最大分数，即 $\textit{dfs}(i-1, j, k')$。所以有 $\textit{dfs}(i,j,k) = \textit{dfs}(i-1, j, k') + x$。
如果最后一步从 $(i,j-1)$ 走到 $(i,j)$，那么问题变成从 $(0,0)$ 走到 $(i,j-1)$，在总花费不超过 $k'$ 的情况下，可以获得的最大分数，即 $\textit{dfs}(i, j-1, k')$。所以有 $\textit{dfs}(i,j,k) = \textit{dfs}(i, j-1, k') + x$。

两种情况取最大值，得

$$
\textit{dfs}(i,j,k) = \max(\textit{dfs}(i-1, j, k'), \textit{dfs}(i, j-1, k')) + x
$$

递归边界：

如果 $i,j,k$ 中的任意一个数小于 $0$，不合法，返回 $-\infty$，从而保证 $\max$ 不会取到不合法的状态。
$\textit{dfs}(0,0,k)=0$。注意题目保证 $\textit{grid}[0][0] = 0$。

递归入口：$\textit{dfs}(m-1,n-1,k)$，这是原问题，也是答案。

记忆化搜索

原理见动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，包含把记忆化搜索 1:1 翻译成递推的技巧。

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

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0 or j < 0 or k < 0:  # 出界或者总花费超了
                return -inf
            if i == 0 and j == 0:
                return 0  # 题目保证 grid[0][0] = 0
            x = grid[i][j]
            if x > 0:
                k -= 1
            return max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x

        ans = dfs(len(grid) - 1, len(grid[0]) - 1, k)
        dfs.cache_clear()  # 避免超出内存限制
        return -1 if ans < 0 else ans

###java

class Solution {
    public int maxPathScore(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] memo = new int[m][n][k + 1];
        for (int[][] mat : memo) {
            for (int[] row : mat) {
                Arrays.fill(row, -1);
            }
        }
        int ans = dfs(m - 1, n - 1, k, grid, memo);
        return ans < 0 ? -1 : ans;
    }

    private int dfs(int i, int j, int k, int[][] grid, int[][][] memo) {
        if (i < 0 || j < 0 || k < 0) { // 出界或者总花费超了
            return Integer.MIN_VALUE;
        }
        if (i == 0 && j == 0) {
            return 0; // 题目保证 grid[0][0] = 0
        }
        if (memo[i][j][k] != -1) {
            return memo[i][j][k];
        }
        int x = grid[i][j];
        int newK = x > 0 ? k - 1 : k;
        return memo[i][j][k] = Math.max(dfs(i - 1, j, newK, grid, memo), dfs(i, j - 1, newK, grid, memo)) + x;
    }
}

###cpp

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector(n, vector<int>(k + 1, -1)));

        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0 || j < 0 || k < 0) { // 出界或者总花费超了
                return INT_MIN;
            }
            if (i == 0 && j == 0) {
                return 0; // 题目保证 grid[0][0] = 0
            }
            int& res = memo[i][j][k];
            if (res != -1) {
                return res;
            }
            int x = grid[i][j];
            if (x > 0) {
                k--;
            }
            return res = max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x;
        };

        int ans = dfs(m - 1, n - 1, k);
        return ans < 0 ? -1 : ans;
    }
};

###go

func maxPathScore(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
memo := make([][][]int, m)
for i := range memo {
memo[i] = make([][]int, n)
for j := range memo[i] {
memo[i][j] = make([]int, k+1)
for p := range memo[i][j] {
memo[i][j][p] = -1
}
}
}

var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 || k < 0 { // 出界或者总花费超了
return math.MinInt
}
if i == 0 && j == 0 {
return 0 // 题目保证 grid[0][0] = 0
}
p := &memo[i][j][k]
if *p != -1 {
return *p
}
x := grid[i][j]
if x > 0 {
k--
}
res := max(dfs(i-1, j, k), dfs(i, j-1, k)) + x
*p = res
return res
}

ans := dfs(m-1, n-1, k)
if ans < 0 {
return -1
}
return ans
}

递推

把 $f[0][1]$（或者 $f[1][0]$）除了首项都初始化成 $0$，这样 $f[1][1]$ 可以用递推式计算，无需特判。

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def maxPathScore(self, grid: List[List[int]], K: int) -> int:
        m, n = len(grid), len(grid[0])
        f = [[[-inf] * (K + 2) for _ in range(n + 1)] for _ in range(m + 1)]
        f[0][1][1:] = [0] * (K + 1)

        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                for k in range(K + 1):
                    new_k = k - 1 if x else k
                    f[i + 1][j + 1][k + 1] = max(f[i][j + 1][new_k + 1], f[i + 1][j][new_k + 1]) + x

        ans = f[m][n][-1]
        return -1 if ans < 0 else ans

###java

class Solution {
    public int maxPathScore(int[][] grid, int K) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] f = new int[m + 1][n + 1][K + 2];
        for (int[][] mat : f) {
            for (int[] row : mat) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }
        }
        Arrays.fill(f[0][1], 1, K + 2, 0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                for (int k = 0; k <= K; k++) {
                    int newK = x > 0 ? k - 1 : k;
                    f[i + 1][j + 1][k + 1] = Math.max(f[i][j + 1][newK + 1], f[i + 1][j][newK + 1]) + x;
                }
            }
        }

        int ans = f[m][n][K + 1];
        return ans < 0 ? -1 : ans;
    }
}

###cpp

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int K) {
        int m = grid.size(), n = grid[0].size();
        vector f(m + 1, vector(n + 1, vector<int>(K + 2, INT_MIN)));
        ranges::fill(f[0][1].begin() + 1, f[0][1].end(), 0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                for (int k = 0; k <= K; k++) {
                    int new_k = k - (x > 0);
                    f[i + 1][j + 1][k + 1] = max(f[i][j + 1][new_k + 1], f[i + 1][j][new_k + 1]) + x;
                }
            }
        }

        int ans = f[m][n][K + 1];
        return ans < 0 ? -1 : ans;
    }
};

###go

func maxPathScore(grid [][]int, K int) int {
m, n := len(grid), len(grid[0])
f := make([][][]int, m+1)
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, K+2)
for k := range f[i][j] {
f[i][j][k] = math.MinInt
}
}
}
for k := 1; k < K+2; k++ {
f[0][1][k] = 0
}

for i, row := range grid {
for j, x := range row {
for k := range K + 1 {
newK := k
if x > 0 {
newK--
}
f[i+1][j+1][k+1] = max(f[i][j+1][newK+1], f[i+1][j][newK+1]) + x
}
}
}

ans := f[m][n][K+1]
if ans < 0 {
return -1
}
return ans
}

复杂度分析

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

空间优化

去掉第一个维度。

为了避免覆盖状态 $f[i][j+1][\textit{newK}+1]$，$k$ 要倒序枚举（类似 0-1 背包）。

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def maxPathScore(self, grid: List[List[int]], K: int) -> int:
        n = len(grid[0])
        f = [[-inf] * (K + 2) for _ in range(n + 1)]
        f[1][1:] = [0] * (K + 1)

        for row in grid:
            for j, x in enumerate(row):
                for k in range(K, -1, -1):
                    new_k = k - 1 if x else k
                    f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x

        ans = f[n][-1]
        return -1 if ans < 0 else ans

###java

class Solution {
    public int maxPathScore(int[][] grid, int K) {
        int n = grid[0].length;
        int[][] f = new int[n + 1][K + 2];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        Arrays.fill(f[1], 1, K + 2, 0);

        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                int x = row[j];
                for (int k = K; k >= 0; k--) {
                    int newK = x > 0 ? k - 1 : k;
                    f[j + 1][k + 1] = Math.max(f[j + 1][newK + 1], f[j][newK + 1]) + x;
                }
            }
        }

        int ans = f[n][K + 1];
        return ans < 0 ? -1 : ans;
    }
}

###cpp

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int K) {
        int n = grid[0].size();
        vector f(n + 1, vector<int>(K + 2, INT_MIN));
        ranges::fill(f[1].begin() + 1, f[1].end(), 0);

        for (auto& row : grid) {
            for (int j = 0; j < n; j++) {
                int x = row[j];
                for (int k = K; k >= 0; k--) {
                    int new_k = k - (x > 0);
                    f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x;
                }
            }
        }

        int ans = f[n][K + 1];
        return ans < 0 ? -1 : ans;
    }
};

###go

func maxPathScore(grid [][]int, K int) int {
n := len(grid[0])
f := make([][]int, n+1)
for j := range f {
f[j] = make([]int, K+2)
for k := range f[j] {
f[j][k] = math.MinInt
}
}
for k := 1; k < K+2; k++ {
f[1][k] = 0
}

for _, row := range grid {
for j, x := range row {
for k := K; k >= 0; k-- {
newK := k
if x > 0 {
newK--
}
f[j+1][k+1] = max(f[j+1][newK+1], f[j][newK+1]) + x
}
}
}

ans := f[n][K+1]
if ans < 0 {
return -1
}
return ans
}

复杂度分析

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

优化循环次数

从 $(0,0)$ 移动到 $(m-1,n-1)$，至多花费 $m+n-2$（注意题目保证 $\textit{grid}[0][0] = 0$）。所以可以把 $K$ 更新为 $\min(K, m+n-2)$。

此外，从 $(0,0)$ 移动到 $(i,j)$ 至多花费 $i+j$，所以最内层循环的 $k$ 最大是 $\min(K,i+j)$。

改成这种写法后，由于 $f$ 的定义是「至多」，$f[i][j][>i+j]$ 的状态本该更新，但没有更新。所以最后返回的是 $\max(f[m][n])$。

也可以把 $f$ 的定义改成「恰好」，这样只需要把 $f[0][1][1]$ 初始化成 $0$，其余均为 $-\infty$。

此外，可以加一个特判，如果从起点到终点的最小花费都大于 $K$，那么不存在有效路径，返回 $-1$。做法类似 64. 最小路径和，我的题解。

注：更精细的写法是，写一个额外的 DP，计算起点到每个位置的最大花费。

###py

# 手写 min max 更快
fmin = lambda a, b: b if b < a else a
fmax = lambda a, b: b if b > a else a

class Solution:
    # 64. 最小路径和
    def minPathSum(self, grid: List[List[int]]) -> int:
        f = [inf] * (len(grid[0]) + 1)
        f[1] = 0
        for row in grid:
            for j, x in enumerate(row):
                f[j + 1] = fmin(f[j], f[j + 1]) + fmin(x, 1)  # 值大于 0 的单元格花费 1
        return f[-1]

    def maxPathScore(self, grid: List[List[int]], K: int) -> int:
        if self.minPathSum(grid) > K:
            return -1

        m, n = len(grid), len(grid[0])
        K = fmin(K, m + n - 2)  # 至多花费 m+n-2
        f = [[-inf] * (K + 2) for _ in range(n + 1)]
        f[1][1] = 0

        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                for k in range(fmin(K, i + j), -1, -1):  # 从 (0,0) 到 (i,j) 至多花费 i+j
                    new_k = k - 1 if x else k
                    f[j + 1][k + 1] = fmax(f[j + 1][new_k + 1], f[j][new_k + 1]) + x

        return max(f[n])

###java

class Solution {
    public int maxPathScore(int[][] grid, int K) {
        if (minPathSum(grid) > K) {
            return -1;
        }

        int m = grid.length;
        int n = grid[0].length;
        K = Math.min(K, m + n - 2); // 至多花费 m+n-2
        int[][] f = new int[n + 1][K + 2];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        f[1][1] = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                for (int k = Math.min(K, i + j); k >= 0; k--) { // 从 (0,0) 到 (i,j) 至多花费 i+j
                    int newK = x > 0 ? k - 1 : k;
                    f[j + 1][k + 1] = Math.max(f[j + 1][newK + 1], f[j][newK + 1]) + x;
                }
            }
        }

        int ans = 0;
        for (int x : f[n]) {
            ans = Math.max(ans, x);
        }
        return ans;
    }

    // 64. 最小路径和
    private int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[1] = 0;
        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                f[j + 1] = Math.min(f[j], f[j + 1]) + Math.min(row[j], 1); // 值大于 0 的单元格花费 1
            }
        }
        return f[n];
    }
}

###cpp

class Solution {
    // 64. 最小路径和
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid[0].size();
        vector<int> f(n + 1, INT_MAX);
        f[1] = 0;
        for (auto& row : grid) {
            for (int j = 0; j < n; j++) {
                f[j + 1] = min(f[j], f[j + 1]) + min(row[j], 1); // 值大于 0 的单元格花费 1
            }
        }
        return f[n];
    }

public:
    int maxPathScore(vector<vector<int>>& grid, int K) {
        if (minPathSum(grid) > K) {
            return -1;
        }

        int m = grid.size(), n = grid[0].size();
        K = min(K, m + n - 2); // 至多花费 m+n-2
        vector f(n + 1, vector<int>(K + 2, INT_MIN));
        f[1][1] = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                for (int k = min(K, i + j); k >= 0; k--) { // 从 (0,0) 到 (i,j) 至多花费 i+j
                    int new_k = k - (x > 0);
                    f[j + 1][k + 1] = max(f[j + 1][new_k + 1], f[j][new_k + 1]) + x;
                }
            }
        }

        return ranges::max(f[n]);
    }
};

###go

// 64. 最小路径和
func minPathSum(grid [][]int) int {
n := len(grid[0])
f := make([]int, n+1)
for j := range f {
f[j] = math.MaxInt
}
f[1] = 0
for _, row := range grid {
for j, x := range row {
f[j+1] = min(f[j], f[j+1]) + min(x, 1) // 值大于 0 的单元格花费 1
}
}
return f[n]
}

func maxPathScore(grid [][]int, K int) int {
if minPathSum(grid) > K {
return -1
}

m, n := len(grid), len(grid[0])
K = min(K, m+n-2) // 至多花费 m+n-2
f := make([][]int, n+1)
for j := range f {
f[j] = make([]int, K+2)
for k := range f[j] {
f[j][k] = math.MinInt
}
}
f[1][1] = 0

for i, row := range grid {
for j, x := range row {
for k := min(K, i+j); k >= 0; k-- { // 从 (0,0) 到 (i,j) 至多花费 i+j
newK := k
if x > 0 {
newK--
}
f[j+1][k+1] = max(f[j+1][newK+1], f[j][newK+1]) + x
}
}
}

return slices.Max(f[n])
}

复杂度分析

时间复杂度：$\mathcal{O}(mn\cdot\min(k,m+n))$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
空间复杂度：$\mathcal{O}(n\cdot\min(k,m+n))$。

专题训练

见下面动态规划题单的「二、网格图 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

【图解】DP 及其优化：从 n^4 到 n^3 到 n^2（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2024年7月21日 21:37

一、从超时做法说起

从 $\mathcal{O}(n^4)$ 的 DP 开始。

要想知道第 $j$ 列的哪些行的 $\textit{grid}[i][j]$ 被计入总分，我们需要知道：

第 $j+1$ 列有多少个黑色格子（下文简称为黑格）。
第 $j$ 列有多少个黑格。
第 $j-1$ 列有多少个黑格。

定义 $\textit{dfs}(j,\textit{cur},\textit{pre})$ 表示考虑第 $0$ 列到第 $j$ 列，其中第 $j+1$ 列有 $\textit{pre}$ 个黑格、第 $j$ 列有 $\textit{cur}$ 个黑格，返回在第 $0$ 列到第 $j$ 列中能得到的最大总分。

枚举第 $j-1$ 列有 $\textit{nxt}$ 个黑格，问题变成：

考虑第 $0$ 列到第 $j-1$ 列，其中第 $j$ 列有 $\textit{cur}$ 个黑格，第 $j-1$ 列有 $\textit{nxt}$ 个黑格，在第 $0$ 列到第 $j-1$ 列中能得到最大总分，即 $\textit{dfs}(j-1,\textit{nxt},\textit{cur})$。

定义 $s$ 为 $\textit{grid}[\textit{cur}][j]$ 到 $\textit{grid}[\max(\textit{nxt},\textit{pre})-1][j]$ 的元素和，如果 $\max(\textit{nxt},\textit{pre}) \le \textit{cur}$ 则 $s=0$。

用 $\textit{dfs}(j-1,\textit{nxt},\textit{cur}) + s$ 更新 $\textit{dfs}(j,\textit{cur},\textit{pre})$ 的最大值。

递归边界：$j=0$ 时返回 $s$。

递归入口：$\max\limits_{i=0}^{n} \textit{dfs}(n-1,i,0)$。枚举第 $n-1$ 列有 $i$ 个黑格，取递归结果的最大值，作为答案。

由于做法超时，这里仅展示 Python 代码。

###py

# 超时代码
class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 每列的前缀和（从上到下）
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]

        # cur 表示第 j 列的黑格个数
        # pre 表示第 j+1 列的黑格个数
        @cache
        def dfs(j: int, cur: int, pre: int) -> int:
            if j == 0:
                return col_sum[0][pre] - col_sum[0][cur] if pre > cur else 0
            res = 0
            # 枚举第 j-1 列有 nxt 个黑格
            for nxt in range(n + 1):
                s = col_sum[j][max(nxt, pre)] - col_sum[j][cur] if max(nxt, pre) > cur else 0
                res = max(res, dfs(j - 1, nxt, cur) + s)
            return res
        # 枚举第 n-1 列有 i 个黑格
        return max(dfs(n - 1, i, 0) for i in range(n + 1))

复杂度分析（超时）

时间复杂度：$\mathcal{O}(n^4)$，其中 $n$ 是 $\textit{grid}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n^3)$，单个状态的计算时间为 $\mathcal{O}(n)$，所以动态规划的时间复杂度为 $\mathcal{O}(n^4)$。
空间复杂度：$\mathcal{O}(n^3)$。

二、记忆化搜索

如果不考虑第 $j-1$ 列呢？不去枚举 $\textit{nxt}$，而是枚举 $\textit{cur}$ 呢？

我们的原则是，在从右往左递归的过程中，只把第 $j$ 列或者第 $j+1$ 列的格子计入总分，不考虑第 $j-1$ 列的格子。

如何不重不漏地统计呢？

定义 $\textit{dfs}(j,\textit{pre},\textit{dec})$ 表示考虑第 $0$ 列到第 $j$ 列，其中：

第 $j+1$ 列有 $\textit{pre}$ 个黑格；
第 $j+1$ 列和第 $j+2$ 列的黑格个数的大小关系用布尔值 $\textit{dec}$ 表示，只有当第 $j+1$ 列的黑格个数小于第 $j+2$ 列的黑格个数时 $\textit{dec}$ 才为 $\texttt{true}$。

在上述约束下，返回第 $0$ 列到第 $j$ 列中能得到的最大总分。

枚举第 $j$ 列有 $\textit{cur}$ 个黑格，按照上图中的四种情况计算。

递归边界：$j=-1$ 时返回 $0$。

递归入口：$\max\limits_{i=0}^{n} \textit{dfs}(n-2,i,0)$。枚举第 $n-1$ 列有 $i$ 个黑格，取递归结果的最大值，作为答案。注意第 $n-1$ 列的格子会在 $j=n-2$ 中计入。

###py

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 每列的前缀和（从上到下）
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]

        # pre 表示第 j+1 列的黑格个数
        # dec=True 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
        @cache
        def dfs(j: int, pre: int, dec: bool) -> int:
            if j < 0:
                return 0
            res = 0
            # 枚举第 j 列有 cur 个黑格
            for cur in range(n + 1):
                if cur == pre:  # 情况一：相等
                    # 没有可以计入总分的格子
                    res = max(res, dfs(j - 1, cur, False))
                elif cur < pre:  # 情况二：右边黑格多
                    # 第 j 列的第 [cur, pre) 行的格子可以计入总分
                    res = max(res, dfs(j - 1, cur, True) + col_sum[j][pre] - col_sum[j][cur])
                elif not dec:  # 情况三：cur > pre >= 第 j+2 列的黑格个数
                    # 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                    res = max(res, dfs(j - 1, cur, False) + col_sum[j + 1][cur] - col_sum[j + 1][pre])
                elif pre == 0:  # 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                    # 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                    # 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                    # 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                    res = max(res, dfs(j - 1, cur, False))
            return res
        # 枚举第 n-1 列有 i 个黑格
        return max(dfs(n - 2, i, False) for i in range(n + 1))

###java

class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        // 每列的前缀和（从上到下）
        long[][] colSum = new long[n][n + 1];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];
            }
        }

        long[][][] memo = new long[n - 1][n + 1][2];
        for (long[][] mat : memo) {
            for (long[] row : mat) {
                Arrays.fill(row, -1); // -1 表示没有计算过
            }
        }

        // 枚举第 n-1 列有 i 个黑格
        long ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = Math.max(ans, dfs(n - 2, i, 0, colSum, memo));
        }
        return ans;
    }

    // pre 表示第 j+1 列的黑格个数
    // dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
    private long dfs(int j, int pre, int dec, long[][] colSum, long[][][] memo) {
        if (j < 0) {
            return 0;
        }
        if (memo[j][pre][dec] != -1) { // 之前计算过
            return memo[j][pre][dec];
        }
        long res = 0;
        // 枚举第 j 列有 cur 个黑格
        for (int cur = 0; cur <= colSum.length; cur++) {
            if (cur == pre) { // 情况一：相等
                // 没有可以计入总分的格子
                res = Math.max(res, dfs(j - 1, cur, 0, colSum, memo));
            } else if (cur < pre) { // 情况二：右边黑格多
                // 第 j 列的第 [cur, pre) 行的格子可以计入总分
                res = Math.max(res, dfs(j - 1, cur, 1, colSum, memo) + colSum[j][pre] - colSum[j][cur]);
            } else if (dec == 0) { // 情况三：cur > pre >= 第 j+2 列的黑格个数
                // 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                res = Math.max(res, dfs(j - 1, cur, 0, colSum, memo) + colSum[j + 1][cur] - colSum[j + 1][pre]);
            } else if (pre == 0) { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                // 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                // 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                // 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                res = Math.max(res, dfs(j - 1, cur, 0, colSum, memo));
            }
        }
        return memo[j][pre][dec] = res; // 记忆化
    }
}

###cpp

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        // 每列的前缀和（从上到下）
        vector<vector<long long>> col_sum(n, vector<long long>(n + 1));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
            }
        }

        vector<vector<array<long long, 2>>> memo(n - 1, vector<array<long long, 2>>(n + 1, {-1, -1})); // -1 表示没有计算过
        // pre 表示第 j+1 列的黑格个数
        // dec=true 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
        auto dfs = [&](auto&& dfs, int j, int pre, bool dec) -> long long {
            if (j < 0) {
                return 0;
            }
            auto& res = memo[j][pre][dec]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            // 枚举第 j 列有 cur 个黑格
            for (int cur = 0; cur <= n; cur++) {
                if (cur == pre) { // 情况一：相等
                    // 没有可以计入总分的格子
                    res = max(res, dfs(dfs, j - 1, cur, false));
                } else if (cur < pre) { // 情况二：右边黑格多
                    // 第 j 列的第 [cur, pre) 行的格子可以计入总分
                    res = max(res, dfs(dfs, j - 1, cur, true) + col_sum[j][pre] - col_sum[j][cur]);
                } else if (!dec) { // 情况三：cur > pre >= 第 j+2 列的黑格个数
                    // 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                    res = max(res, dfs(dfs, j - 1, cur, false) + col_sum[j + 1][cur] - col_sum[j + 1][pre]);
                } else if (pre == 0) { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                    // 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                    // 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                    // 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                    res = max(res, dfs(dfs, j - 1, cur, false));
                }
            }
            return res;
        };

        // 枚举第 n-1 列有 i 个黑格
        long long ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = max(ans, dfs(dfs, n - 2, i, false));
        }
        return ans;
    }
};

###go

func maximumScore(grid [][]int) (ans int64) {
n := len(grid)
// 每列的前缀和（从上到下）
colSum := make([][]int64, n)
for j := range colSum {
colSum[j] = make([]int64, n+1)
for i, row := range grid {
colSum[j][i+1] = colSum[j][i] + int64(row[j])
}
}

memo := make([][][2]int64, n-1)
for i := range memo {
memo[i] = make([][2]int64, n+1)
for j := range memo[i] {
memo[i][j] = [2]int64{-1, -1} // -1 表示没有计算过
}
}
var dfs func(int, int, int) int64
dfs = func(j, pre, dec int) int64 {
if j < 0 {
return 0
}
p := &memo[j][pre][dec]
if *p != -1 { // 之前计算过
return *p
}
res := int64(0)
// 枚举第 j 列有 cur 个黑格
for cur := 0; cur <= n; cur++ {
if cur == pre { // 情况一：相等
// 没有可以计入总分的格子
res = max(res, dfs(j-1, cur, 0))
} else if cur < pre { // 情况二：右边黑格多
// 第 j 列的第 [cur, pre) 行的格子可以计入总分
res = max(res, dfs(j-1, cur, 1)+colSum[j][pre]-colSum[j][cur])
} else if dec == 0 { // 情况三：cur > pre >= 第 j+2 列的黑格个数
// 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
res = max(res, dfs(j-1, cur, 0)+colSum[j+1][cur]-colSum[j+1][pre])
} else if pre == 0 { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
// 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
// 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
// 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
res = max(res, dfs(j-1, cur, 0))
}
}
*p = res // 记忆化
return res
}

// 枚举第 n-1 列有 i 个黑格
for i := 0; i <= n; i++ {
ans = max(ans, dfs(n-2, i, 0))
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n^3)$，其中 $n$ 是 $\textit{grid}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n^2)$，单个状态的计算时间为 $\mathcal{O}(n)$，所以动态规划的时间复杂度为 $\mathcal{O}(n^3)$。
空间复杂度：$\mathcal{O}(n^2)$。

三、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体请看视频讲解动态规划入门：从记忆化搜索到递推，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

$f[j+1][\textit{pre}][\textit{dec}]$ 的定义和 $\textit{dfs}(j,\textit{pre},\textit{dec})$ 的定义是一样的。注意这里是 $j+1$ 不是 $j$，因为要避免 $j=-1$ 时出现负数下标。

初始值 $f[0][\textit{pre}][\textit{dec}]=0$，翻译自递归边界。

答案为 $\max\limits_{i=0}^{n} f[n-1][i][0]$，翻译自递归入口。

###py

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 每列的前缀和（从上到下）
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]
        f = [[[0, 0] for _ in range(n + 1)] for _ in range(n)]
        for j in range(n - 1):
            # pre 表示第 j+1 列的黑格个数
            for pre in range(n + 1):
                # dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
                for dec in range(2):
                    res = 0
                    # 枚举第 j 列有 cur 个黑格
                    for cur in range(n + 1):
                        if cur == pre:  # 情况一：相等
                            # 没有可以计入总分的格子
                            res = max(res, f[j][cur][0])
                        elif cur < pre:  # 情况二：右边黑格多
                            # 第 j 列的第 [cur, pre) 行的格子可以计入总分
                            res = max(res, f[j][cur][1] + col_sum[j][pre] - col_sum[j][cur])
                        elif dec == 0:  # 情况三：cur > pre >= 第 j+2 列的黑格个数
                            # 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                            res = max(res, f[j][cur][0] + col_sum[j + 1][cur] - col_sum[j + 1][pre])
                        elif pre == 0:  # 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                            # 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                            # 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                            # 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                            res = max(res, f[j][cur][0])
                    f[j + 1][pre][dec] = res
        # 枚举第 n-1 列有 i 个黑格
        return max(f[-1][i][0] for i in range(n + 1))

###java

class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        // 每列的前缀和（从上到下）
        long[][] colSum = new long[n][n + 1];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];
            }
        }

        long[][][] f = new long[n][n + 1][2];
        for (int j = 0; j < n - 1; j++) {
            // pre 表示第 j+1 列的黑格个数
            for (int pre = 0; pre <= n; pre++) {
                // dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
                for (int dec = 0; dec < 2; dec++) {
                    long res = 0;
                    // 枚举第 j 列有 cur 个黑格
                    for (int cur = 0; cur <= n; cur++) {
                        if (cur == pre) { // 情况一：相等
                            // 没有可以计入总分的格子
                            res = Math.max(res, f[j][cur][0]);
                        } else if (cur < pre) { // 情况二：右边黑格多
                            // 第 j 列的第 [cur, pre) 行的格子可以计入总分
                            res = Math.max(res, f[j][cur][1] + colSum[j][pre] - colSum[j][cur]);
                        } else if (dec == 0) { // 情况三：cur > pre >= 第 j+2 列的黑格个数
                            // 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                            res = Math.max(res, f[j][cur][0] + colSum[j + 1][cur] - colSum[j + 1][pre]);
                        } else if (pre == 0) { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                            // 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                            // 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                            // 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                            res = Math.max(res, f[j][cur][0]);
                        }
                    }
                    f[j + 1][pre][dec] = res;
                }
            }
        }

        long ans = 0;
        for (long[] row : f[n - 1]) {
            ans = Math.max(ans, row[0]);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        // 每列的前缀和（从上到下）
        vector<vector<long long>> col_sum(n, vector<long long>(n + 1));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
            }
        }

        vector<vector<array<long long, 2>>> f(n, vector<array<long long, 2>>(n + 1));
        for (int j = 0; j < n - 1; j++) {
            // pre 表示第 j+1 列的黑格个数
            for (int pre = 0; pre <= n; pre++) {
                // dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
                for (int dec = 0; dec < 2; dec++) {
                    auto& res = f[j + 1][pre][dec];
                    // 枚举第 j 列有 cur 个黑格
                    for (int cur = 0; cur <= n; cur++) {
                        if (cur == pre) { // 情况一：相等
                            // 没有可以计入总分的格子
                            res = max(res, f[j][cur][0]);
                        } else if (cur < pre) { // 情况二：右边黑格多
                            // 第 j 列的第 [cur, pre) 行的格子可以计入总分
                            res = max(res, f[j][cur][1] + col_sum[j][pre] - col_sum[j][cur]);
                        } else if (dec == 0) { // 情况三：cur > pre >= 第 j+2 列的黑格个数
                            // 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                            res = max(res, f[j][cur][0] + col_sum[j + 1][cur] - col_sum[j + 1][pre]);
                        } else if (pre == 0) { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                            // 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                            // 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                            // 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                            res = max(res, f[j][cur][0]);
                        }
                    }
                }
            }
        }

        // 枚举第 n-1 列有 i 个黑格
        long long ans = 0;
        for (auto& row : f[n - 1]) {
            ans = max(ans, row[0]);
        }
        return ans;
    }
};

###go

func maximumScore(grid [][]int) (ans int64) {
n := len(grid)
// 每列的前缀和（从上到下）
colSum := make([][]int64, n)
for j := range colSum {
colSum[j] = make([]int64, n+1)
for i, row := range grid {
colSum[j][i+1] = colSum[j][i] + int64(row[j])
}
}

f := make([][][2]int64, n)
for j := range f {
f[j] = make([][2]int64, n+1)
}
for j := 0; j < n-1; j++ {
// pre 表示第 j+1 列的黑格个数
for pre := 0; pre <= n; pre++ {
// dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
for dec := 0; dec < 2; dec++ {
res := int64(0)
// 枚举第 j 列有 cur 个黑格
for cur := 0; cur <= n; cur++ {
if cur == pre { // 情况一：相等
// 没有可以计入总分的格子
res = max(res, f[j][cur][0])
} else if cur < pre { // 情况二：右边黑格多
// 第 j 列的第 [cur, pre) 行的格子可以计入总分
res = max(res, f[j][cur][1]+colSum[j][pre]-colSum[j][cur])
} else if dec == 0 { // 情况三：cur > pre >= 第 j+2 列的黑格个数
// 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
res = max(res, f[j][cur][0]+colSum[j+1][cur]-colSum[j+1][pre])
} else if pre == 0 { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
// 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
// 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
// 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
res = max(res, f[j][cur][0])
}
}
f[j+1][pre][dec] = res
}
}
}

for _, row := range f[n-1] {
ans = max(ans, row[0])
}
return ans
}

复杂度分析

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

四、时间优化

把最内层的枚举 $\textit{cur}$ 的循环优化掉。

首先计算 $\textit{pre}>0$ 的状态，然后单独计算 $\textit{pre}=0$ 的状态。

1) pre > 0 且 dec = 1

$\textit{pre}> 0$ 的状态，没有情况四。

对于 $f[j+1][\textit{pre}][1]$，需要计算 $f[j][\textit{pre}][0]$（情况一）与下式（情况二）的最大值：

$$
\begin{aligned}
& \max\limits_{\textit{cur}=0}^{\textit{pre}-1} {f[j][\textit{cur}][1] + \textit{colSum}[j][\textit{pre}] - \textit{colSum}[j][\textit{cur}]} \
={} & \textit{colSum}[j][\textit{pre}] + \max\limits_{\textit{cur}=0}^{\textit{pre}-1} {f[j][\textit{cur}][1] - \textit{colSum}[j][\textit{cur}]} \
\end{aligned}
$$

其中

$$
\max\limits_{\textit{cur}=0}^{\textit{pre}-1} {f[j][\textit{cur}][1] - \textit{colSum}[j][\textit{cur}]}
$$

可以一边从小到大枚举 $\textit{pre}$，一边用一个变量 $\textit{preMax}$ 维护。

2) pre > 0 且 dec = 0

对于 $f[j+1][\textit{pre}][0]$，除了上面 $\textit{dec}=1$ 要计算的，这里也要计算外，还需要计算下式（情况三）的最大值：

$$
\begin{aligned}
& \max\limits_{\textit{cur}=pre+1}^{n} { f[j][\textit{cur}][0] + \textit{colSum}[j + 1][\textit{cur}] - \textit{colSum}[j + 1][\textit{pre}] } \
={} & - \textit{colSum}[j + 1][\textit{pre}] + \max\limits_{\textit{cur}=pre+1}^{n} { f[j][\textit{cur}][0] + \textit{colSum}[j + 1][\textit{cur}] } \
\end{aligned}
$$

其中

$$
\max\limits_{\textit{cur}=pre+1}^{n} { f[j][\textit{cur}][0] + \textit{colSum}[j + 1][\textit{cur}] }
$$

可以一边从大到小枚举 $\textit{pre}$，一边用一个变量 $\textit{sufMax}$ 维护。

3) pre = 0 且 dec = 0

$\textit{pre}=0$ 的状态，没有情况二。

对于 $f[j+1][0][0]$，需要计算 $f[j][0][0]$（情况一）与下式（情况三）的最大值：

$$
\max\limits_{\textit{cur}=1}^{n} { f[j][\textit{cur}][0] + \textit{colSum}[j + 1][\textit{cur}] }
$$

这正是上面循环结束后的 $\textit{sufMax}$。

此外，由于不可能连续三列全白，所以无需考虑从 $f[j][0][0]$（情况一）转移过来，因此

$$
f[j+1][0][0] = \textit{sufMax}
$$

4) pre = 0 且 dec = 1

对于 $f[j+1][0][1]$，需要计算下式（情况一与情况四）的最大值：

$$
\max\limits_{\textit{cur}=0}^{n} f[j][\textit{cur}][0]
$$

但在 $\textit{pre}=0$ 且 $\textit{dec}=1$ 的前提下，其实只需考虑第 $j$ 列全白（$\textit{cur}=0$）或全黑（$\textit{cur}=n$）两种情况。沿用上文图片中的证明方法，考虑第 $j-1$ 列的黑格个数 $B_{j-1}$：

如果 $B_{j-1} \ge B_j$，第 $j$ 列全白更好。
如果 $B_{j-1} < B_j$，第 $j$ 列多出的段左右都是白格，所以全黑更好。

因此

$$
f[j+1][0][1] = \max(f[j][0][0], f[j][n][0])
$$

###py

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]

        f = [[[0, 0] for _ in range(n + 1)] for _ in range(n)]
        for j in range(n - 1):
            # 用前缀最大值优化
            pre_max = f[j][0][1] - col_sum[j][0]
            for pre in range(1, n + 1):
                f[j + 1][pre][0] = f[j + 1][pre][1] = max(f[j][pre][0], pre_max + col_sum[j][pre])
                pre_max = max(pre_max, f[j][pre][1] - col_sum[j][pre])

            # 用后缀最大值优化
            suf_max = f[j][n][0] + col_sum[j + 1][n]
            for pre in range(n - 1, 0, -1):
                f[j + 1][pre][0] = max(f[j + 1][pre][0], suf_max - col_sum[j + 1][pre])
                suf_max = max(suf_max, f[j][pre][0] + col_sum[j + 1][pre])

            # 单独计算 pre=0 的状态
            f[j + 1][0][0] = suf_max  # 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = max(f[j][0][0], f[j][n][0])  # 第 j 列要么全白，要么全黑

        return max(f[-1][i][0] for i in range(n + 1))

###java

class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        long[][] colSum = new long[n][n + 1];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];
            }
        }

        long[][][] f = new long[n][n + 1][2];
        for (int j = 0; j < n - 1; j++) {
            // 用前缀最大值优化
            long preMax = f[j][0][1] - colSum[j][0];
            for (int pre = 1; pre <= n; pre++) {
                f[j + 1][pre][0] = f[j + 1][pre][1] = Math.max(f[j][pre][0], preMax + colSum[j][pre]);
                preMax = Math.max(preMax, f[j][pre][1] - colSum[j][pre]);
            }

            // 用后缀最大值优化
            long sufMax = f[j][n][0] + colSum[j + 1][n];
            for (int pre = n - 1; pre > 0; pre--) {
                f[j + 1][pre][0] = Math.max(f[j + 1][pre][0], sufMax - colSum[j + 1][pre]);
                sufMax = Math.max(sufMax, f[j][pre][0] + colSum[j + 1][pre]);
            }

            // 单独计算 pre=0 的状态
            f[j + 1][0][0] = sufMax; // 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = Math.max(f[j][0][0], f[j][n][0]); // 第 j 列要么全白，要么全黑
        }

        long ans = 0;
        for (long[] row : f[n - 1]) {
            ans = Math.max(ans, row[0]);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<long long>> col_sum(n, vector<long long>(n + 1));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
            }
        }

        vector<vector<array<long long, 2>>> f(n, vector<array<long long, 2>>(n + 1));
        for (int j = 0; j < n - 1; j++) {
            // 用前缀最大值优化
            long long pre_max = f[j][0][1] - col_sum[j][0];
            for (int pre = 1; pre <= n; pre++) {
                f[j + 1][pre][0] = f[j + 1][pre][1] = max(f[j][pre][0], pre_max + col_sum[j][pre]);
                pre_max = max(pre_max, f[j][pre][1] - col_sum[j][pre]);
            }

            // 用后缀最大值优化
            long long suf_max = f[j][n][0] + col_sum[j + 1][n];
            for (int pre = n - 1; pre > 0; pre--) {
                f[j + 1][pre][0] = max(f[j + 1][pre][0], suf_max - col_sum[j + 1][pre]);
                suf_max = max(suf_max, f[j][pre][0] + col_sum[j + 1][pre]);
            }

            // 单独计算 pre=0 的状态
            f[j + 1][0][0] = suf_max; // 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = max(f[j][0][0], f[j][n][0]); // 第 j 列要么全白，要么全黑
        }

        long long ans = 0;
        for (auto& row : f[n - 1]) {
            ans = max(ans, row[0]);
        }
        return ans;
    }
};

###go

func maximumScore(grid [][]int) (ans int64) {
n := len(grid)
colSum := make([][]int64, n)
for j := range colSum {
colSum[j] = make([]int64, n+1)
for i, row := range grid {
colSum[j][i+1] = colSum[j][i] + int64(row[j])
}
}

f := make([][][2]int64, n)
for j := range f {
f[j] = make([][2]int64, n+1)
}
for j := 0; j < n-1; j++ {
// 用前缀最大值优化
preMax := f[j][0][1] - colSum[j][0]
for pre := 1; pre <= n; pre++ {
f[j+1][pre][0] = max(f[j][pre][0], preMax+colSum[j][pre])
f[j+1][pre][1] = f[j+1][pre][0]
preMax = max(preMax, f[j][pre][1]-colSum[j][pre])
}

// 用后缀最大值优化
sufMax := f[j][n][0] + colSum[j+1][n]
for pre := n - 1; pre > 0; pre-- {
f[j+1][pre][0] = max(f[j+1][pre][0], sufMax-colSum[j+1][pre])
sufMax = max(sufMax, f[j][pre][0]+colSum[j+1][pre])
}

// 单独计算 pre=0 的状态
f[j+1][0][0] = sufMax // 无需考虑 f[j][0][0]，因为不能连续三列全白
f[j+1][0][1] = max(f[j][0][0], f[j][n][0]) // 第 j 列要么全白，要么全黑
}

for _, row := range f[n-1] {
ans = max(ans, row[0])
}
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $\textit{grid}$ 的长度。这是本题的最优复杂度，因为遍历 $\textit{grid}$ 就需要 $\mathcal{O}(n^2)$ 的时间了。
空间复杂度：$\mathcal{O}(n^2)$。

注：空间复杂度可以进一步优化至 $\mathcal{O}(n)$，需要用到滚动数组，并在 DP 的过程中计算列的前缀和。

分类题单

如何科学刷题？

我的题解精选（已分类）

中位数贪心（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2021年10月10日 12:13

先判断是否无解。

例如 $x=2$，我们可以把 $2,4,6,8$ 都变成同一个数，但能把 $2,5$ 变成同一个数吗？不能，在 $x=2$ 的情况下，偶数只能变成偶数，奇数只能变成奇数，无法把偶数和奇数变成同一个数。在 $x=2$ 的情况下，每个数的奇偶性（模 $2$ 的结果）必须都一样，才能变成同一个数。

一般地，对于整数 $k$，我们有 $(\textit{grid}[i][j] + kx)\bmod x = \textit{grid}[i][j]\bmod x$。所以操作后，$\textit{grid}[i][j] \bmod x$ 是不变的。每个数模 $x$ 的结果必须都一样，才能变成同一个数。否则无解，输出 $-1$。

想象操场上有一些人，把这些人聚在一起，怎么移动最迅速？

往「中间」移动是最迅速的。

根据中位数贪心及其证明，把所有数变成 $\textit{grid}$ 的中位数是最优的。

设 $\textit{grid}$ 的中位数为 $\textit{median}$，总操作次数为

$$
\sum_{v\in \textit{grid}}\dfrac{|v - \textit{median}|}{x} = \dfrac{\sum\limits_{v\in \textit{grid}}|v - \textit{median}|}{x}
$$

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        a = []
        target = grid[0][0] % x

        # 1. 判断是否无解
        for row in grid:
            for v in row:
                if v % x != target:  # 每个数模 x 都必须相等
                    return -1
            a += row

        # 2. 计算 grid 的中位数 median
        a.sort()
        median = a[len(a) // 2]

        # 3. 计算操作次数
        return sum(abs(v - median) for v in a) // x

class Solution {
    public int minOperations(int[][] grid, int x) {
        int k = grid.length * grid[0].length;
        int[] a = new int[k];
        int idx = 0;
        int target = grid[0][0] % x;

        // 1. 判断是否无解
        for (int[] row : grid) {
            for (int v : row) {
                if (v % x != target) { // 每个数模 x 都必须相等
                    return -1;
                }
                a[idx++] = v;
            }
        }

        // 2. 计算 grid 的中位数 median
        Arrays.sort(a);
        int median = a[k / 2];

        // 3. 计算操作次数
        int ans = 0;
        for (int v : a) {
            ans += Math.abs(v - median);
        }
        return ans / x;
    }
}

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        int k = grid.size() * grid[0].size();
        vector<int> a;
        a.reserve(k); // 预分配空间
        int target = grid[0][0] % x;
    
        // 1. 判断是否无解
        for (auto& row : grid) {
            for (int v : row) {
                if (v % x != target) { // 每个数模 x 都必须相等
                    return -1;
                }
                a.push_back(v);
            }
        }

        // 2. 计算 grid 的中位数 median
        // ranges::sort(a);
        ranges::nth_element(a, a.begin() + k / 2); // 用快速选择代替排序
        int median = a[k / 2];

        // 3. 计算操作次数
        int ans = 0;
        for (int v : a) {
            ans += abs(v - median);
        }
        return ans / x;
    }
};

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

int minOperations(int** grid, int gridSize, int* gridColSize, int x) {
    int m = gridSize, n = gridColSize[0];
    int* a = malloc(m * n * sizeof(int));
    int k = 0;
    int target = grid[0][0] % x;

    // 1. 判断是否无解
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] % x != target) { // 每个数模 x 都必须相等
                return -1;
            }
            a[k++] = grid[i][j];
        }
    }

    // 2. 计算 grid 的中位数 median
    qsort(a, k, sizeof(int), cmp);
    int median = a[k / 2];

    // 3. 计算操作次数
    int ans = 0;
    for (int i = 0; i < k; i++) {
        ans += abs(a[i] - median);
    }
    free(a);
    return ans / x;
}

func minOperations(grid [][]int, x int) int {
k := len(grid) * len(grid[0])
a := make([]int, 0, k) // 预分配空间
target := grid[0][0] % x

// 1. 判断是否无解
for _, row := range grid {
for _, v := range row {
if v%x != target { // 每个数模 x 都必须相等
return -1
}
}
a = append(a, row...)
}

// 2. 计算 grid 的中位数 median
slices.Sort(a)
median := a[k/2]

// 3. 计算操作次数
ans := 0
for _, v := range a {
ans += abs(v - median)
}
return ans / x
}

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

var minOperations = function(grid, x) {
    const a = [];
    const target = grid[0][0] % x;

    // 1. 判断是否无解
    for (const row of grid) {
        for (const v of row) {
            if (v % x !== target) { // 每个数模 x 都必须相等
                return -1;
            }
            a.push(v);
        }
    }

    // 2. 计算 grid 的中位数 median
    a.sort((a, b) => a - b);
    const median = a[Math.floor(a.length / 2)];

    // 3. 计算操作次数
    let ans = 0;
    for (const v of a) {
        ans += Math.abs(v - median);
    }
    return ans / x;
};

impl Solution {
    pub fn min_operations(grid: Vec<Vec<i32>>, x: i32) -> i32 {
        let k = grid.len() * grid[0].len();
        let mut a = Vec::with_capacity(k); // 预分配空间
        let target = grid[0][0] % x;

        // 1. 判断是否无解
        for row in grid {
            for v in row {
                if v % x != target { // 每个数模 x 都必须相等
                    return -1;
                }
                a.push(v);
            }
        }

        // 2. 计算 grid 的中位数 median
        let median = *a.select_nth_unstable(k / 2).1;

        // 3. 计算操作次数
        a.into_iter().map(|v| (v - median).abs()).sum::<i32>() / x
    }
}

注：如果 $\textit{grid}$ 有负数，模 $x$ 的结果有正有负，不方便判断，此时可以把判断条件改成 (grid[i][j] - grid[0][0]) % x != 0。

复杂度分析

时间复杂度：$\mathcal{O}(mn\log(mn))$ 或 $\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。瓶颈在排序上。用快速选择算法代替排序，可以做到 $\mathcal{O}(mn)$，见 C++ 或 Rust 代码。如果你想手写快速选择算法，可以看 215. 数组中的第K个最大元素，我的题解。
空间复杂度：$\mathcal{O}(mn)$。

专题训练

见下面贪心题单的「§4.5 中位数贪心」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

利用方向向量简化代码逻辑（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2026年4月13日 08:46

我们需要解决两个关键问题：

站在 $(x,y)$，下一步可以往哪些方向移动？
如何判断相邻街道是否连通？示例 2 的街道不是连通的，无法移动。

对于第一个问题，我们可以创建一个方向向量数组，保存每种街道的移动方向。例如：

站在街道 1，我们可以往左或者往右移动，对应的方向向量分别为 $(0,-1)$ 和 $(0,1)$。
站在街道 3，我们可以往左或者往下移动，对应的方向向量分别为 $(0,-1)$ 和 $(1,0)$。

对于第二个问题，如果两条相邻街道可以互相到达，那么这两条街道就是连通的。

如果街道 1 的右边是街道 3，我们可以从街道 1 往右移动到街道 3，也可以从街道 3 往左移动到街道 1。
如果要从街道 1 往右移动，那么只要右边相邻街道能往左移动就行，也就是包含往左的方向向量 $(0,-1)$。
一般地，如果从当前位置往 $(\textit{dx},\textit{dy})$ 方向移动到相邻街道，那么相邻街道必须包含相反的方向向量 $(-\textit{dx},-\textit{dy})$。

###py

DIRS = (
    (),
    ((0, -1), (0, 1)),  # 站在街道 1，可以往左或者往右
    ((-1, 0), (1, 0)),  # 站在街道 2，可以往上或者往下
    ((0, -1), (1, 0)),  # 站在街道 3，可以往左或者往下
    ((0, 1), (1, 0)),   # 站在街道 4，可以往右或者往下
    ((0, -1), (-1, 0)), # 站在街道 5，可以往左或者往上
    ((0, 1), (-1, 0)),  # 站在街道 6，可以往右或者往上
)

class Solution:
    def hasValidPath(self, grid: list[list[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]

        def dfs(x: int, y: int) -> bool:
            if x == m - 1 and y == n - 1:
                return True
            vis[x][y] = True  # 标记 (x, y) 访问过，从而避免重复访问
            for dx, dy in DIRS[grid[x][y]]:  # 枚举下一步往哪走
                i, j = x + dx, y + dy
                if 0 <= i < m and 0 <= j < n and not vis[i][j] and \
                   (-dx, -dy) in DIRS[grid[i][j]] and dfs(i, j):
                    return True
            return False

        return dfs(0, 0)

###java

class Solution {
    private static final int[][][] DIRS = {
        {},
        {{0, -1}, {0, 1}},  // 站在街道 1，可以往左或者往右
        {{-1, 0}, {1, 0}},  // 站在街道 2，可以往上或者往下
        {{0, -1}, {1, 0}},  // 站在街道 3，可以往左或者往下
        {{0, 1}, {1, 0}},   // 站在街道 4，可以往右或者往下
        {{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
        {{0, 1}, {-1, 0}},  // 站在街道 6，可以往右或者往上
    };

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        return dfs(0, 0, grid, vis);
    }

    private boolean dfs(int x, int y, int[][] grid, boolean[][] vis) {
        int m = grid.length;
        int n = grid[x].length;
        if (x == m - 1 && y == n - 1) {
            return true;
        }
        vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
        for (int[] d : DIRS[grid[x][y]]) { // 枚举下一步往哪走
            int i = x + d[0];
            int j = y + d[1];
            if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
                contains(grid[i][j], -d[0], -d[1]) && dfs(i, j, grid, vis)) {
                return true;
            }
        }
        return false;
    }

    // 判断街道 street 是否包含移动方向 (dx, dy)
    private boolean contains(int street, int dx, int dy) {
        int[][] ds = DIRS[street];
        return ds[0][0] == dx && ds[0][1] == dy ||
               ds[1][0] == dx && ds[1][1] == dy;
    }
}

###cpp

class Solution {
    static constexpr int DIRS[7][2][2] = {
        {},
        {{0, -1}, {0, 1}},  // 站在街道 1，可以往左或者往右
        {{-1, 0}, {1, 0}},  // 站在街道 2，可以往上或者往下
        {{0, -1}, {1, 0}},  // 站在街道 3，可以往左或者往下
        {{0, 1}, {1, 0}},   // 站在街道 4，可以往右或者往下
        {{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
        {{0, 1}, {-1, 0}},  // 站在街道 6，可以往右或者往上
    };

    // 判断街道 street 是否包含移动方向 (dx, dy)
    bool contains(int street, int dx, int dy) {
        auto& ds = DIRS[street];
        return ds[0][0] == dx && ds[0][1] == dy ||
               ds[1][0] == dx && ds[1][1] == dy;
    }

public:
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector vis(m, vector<int8_t>(n));

        auto dfs = [&](this auto&& dfs, int x, int y) -> bool {
            if (x == m - 1 && y == n - 1) {
                return true;
            }
            vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
            for (auto& [dx, dy] : DIRS[grid[x][y]]) { // 枚举下一步往哪走
                int i = x + dx, j = y + dy;
                if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
                    contains(grid[i][j], -dx, -dy) && dfs(i, j)) {
                    return true;
                }
            }
            return false;
        };

        return dfs(0, 0);
    }
};

###c

static const int DIRS[7][2][2] = {
    {},
    {{0, -1}, {0, 1}},  // 站在街道 1，可以往左或者往右
    {{-1, 0}, {1, 0}},  // 站在街道 2，可以往上或者往下
    {{0, -1}, {1, 0}},  // 站在街道 3，可以往左或者往下
    {{0, 1}, {1, 0}},   // 站在街道 4，可以往右或者往下
    {{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
    {{0, 1}, {-1, 0}},  // 站在街道 6，可以往右或者往上
};

// 判断街道 street 是否包含移动方向 (dx, dy)
bool contains(int street, int dx, int dy) {
    return DIRS[street][0][0] == dx && DIRS[street][0][1] == dy ||
           DIRS[street][1][0] == dx && DIRS[street][1][1] == dy;
}

bool hasValidPath(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    bool** vis = malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        vis[i] = calloc(n, sizeof(bool));
    }

    bool dfs(int x, int y) {
        if (x == m - 1 && y == n - 1) {
            return true;
        }
        vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
        for (int k = 0; k < 2; k++) { // 枚举下一步往哪走
            int* dir = DIRS[grid[x][y]][k];
            int i = x + dir[0], j = y + dir[1];
            if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
                contains(grid[i][j], -dir[0], -dir[1]) && dfs(i, j)) {
                return true;
            }
        }
        return false;
    }

    bool ans = dfs(0, 0);

    for (int i = 0; i < m; i++) {
        free(vis[i]);
    }
    free(vis);

    return ans;
}

###go

var dirs = [7][2][2]int{
{},
{{0, -1}, {0, 1}},  // 站在街道 1，可以往左或者往右
{{-1, 0}, {1, 0}},  // 站在街道 2，可以往上或者往下
{{0, -1}, {1, 0}},  // 站在街道 3，可以往左或者往下
{{0, 1}, {1, 0}},   // 站在街道 4，可以往右或者往下
{{0, -1}, {-1, 0}}, // 站在街道 5，可以往左或者往上
{{0, 1}, {-1, 0}},  // 站在街道 6，可以往右或者往上
}

// 判断街道 street 是否包含移动方向 dir
func contains(street int, dir [2]int) bool {
// 也可以写 slices.Contains(dirs[street][:], dir)
return dirs[street][0] == dir || dirs[street][1] == dir
}

func hasValidPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}

var dfs func(int, int) bool
dfs = func(x, y int) bool {
if x == m-1 && y == n-1 {
return true
}
vis[x][y] = true // 标记 (x, y) 访问过，从而避免重复访问
for _, d := range dirs[grid[x][y]] { // 枚举下一步往哪走
i, j := x+d[0], y+d[1]
if 0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
contains(grid[i][j], [2]int{-d[0], -d[1]}) && dfs(i, j) {
return true
}
}
return false
}

return dfs(0, 0)
}

###js

const DIRS = [
    [],
    [[0, -1], [0, 1]],  // 站在街道 1，可以往左或者往右
    [[-1, 0], [1, 0]],  // 站在街道 2，可以往上或者往下
    [[0, -1], [1, 0]],  // 站在街道 3，可以往左或者往下
    [[0, 1], [1, 0]],   // 站在街道 4，可以往右或者往下
    [[0, -1], [-1, 0]], // 站在街道 5，可以往左或者往上
    [[0, 1], [-1, 0]],  // 站在街道 6，可以往右或者往上
];

// 判断街道 street 是否包含移动方向 (dx, dy)
function contains(street, dx, dy) {
    const ds = DIRS[street];
    return ds[0][0] === dx && ds[0][1] === dy ||
           ds[1][0] === dx && ds[1][1] === dy;
}

var hasValidPath = function(grid) {
    const m = grid.length, n = grid[0].length;
    const vis = Array.from({ length: m }, () => Array(n).fill(false));

    function dfs(x, y) {
        if (x === m - 1 && y === n - 1) {
            return true;
        }
        vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
        for (const [dx, dy] of DIRS[grid[x][y]]) { // 枚举下一步往哪走
            const i = x + dx, j = y + dy;
            if (0 <= i && i < m && 0 <= j && j < n && !vis[i][j] &&
                contains(grid[i][j], -dx, -dy) && dfs(i, j)) {
                return true;
            }
        }
        return false;
    }

    return dfs(0, 0);
};

###rust

impl Solution {
    const DIRS: [[(i32, i32); 2]; 7] = [
        [(0, 0), (0, 0)],
        [(0, -1), (0, 1)],  // 站在街道 1，可以往左或者往右
        [(-1, 0), (1, 0)],  // 站在街道 2，可以往上或者往下
        [(0, -1), (1, 0)],  // 站在街道 3，可以往左或者往下
        [(0, 1), (1, 0)],   // 站在街道 4，可以往右或者往下
        [(0, -1), (-1, 0)], // 站在街道 5，可以往左或者往上
        [(0, 1), (-1, 0)],  // 站在街道 6，可以往右或者往上
    ];

    // 判断街道 street 是否包含移动方向 dir
    fn contains(street: i32, dir: (i32, i32)) -> bool {
        let ds = Self::DIRS[street as usize];
        ds[0] == dir || ds[1] == dir
    }

    pub fn has_valid_path(grid: Vec<Vec<i32>>) -> bool {
        fn dfs(x: usize, y: usize, grid: &[Vec<i32>], vis: &mut [Vec<bool>]) -> bool {
            let m = grid.len();
            let n = grid[x].len();
            if x == m - 1 && y == n - 1 {
                return true;
            }
            vis[x][y] = true; // 标记 (x, y) 访问过，从而避免重复访问
            for &(dx, dy) in Solution::DIRS[grid[x][y] as usize].iter() { // 枚举下一步往哪走
                let i = x + dx as usize;
                let j = y + dy as usize;
                if i < m && j < n && !vis[i][j] &&
                   Solution::contains(grid[i][j], (-dx, -dy)) && dfs(i, j, grid, vis) {
                    return true;
                }
            }
            false
        }

        let m = grid.len();
        let n = grid[0].len();
        let mut vis = vec![vec![false; n]; m];
        dfs(0, 0, &grid, &mut vis)
    }
}

复杂度分析

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

专题训练

见下面网格图题单的「一、网格图 DFS」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

网格图 DFS（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2026年4月16日 08:37

在 DFS 的过程中，如果发现了一个之前访问过的同值格子，那么：

如果我们从 $(x,y)$ 移动一步到 $(i,j)$，再从 $(i,j)$ 移动一步到 $(x,y)$，这的确是个环，但长度只有 $2$，不满足要求。所以我们规定，不能立刻回头。在 DFS 的过程中，额外传入上一步的位置 $(\textit{px},\textit{py})$，并禁止从当前位置移动到上一步的位置。
如果我们从 $(x,y)$ 移动一步到 $(i,j)$，且 $(i,j)\ne (\textit{px},\textit{py})$，且 $(i,j)$ 之前访问过，那么就找到了一个长度至少为 $4$ 的环。

问：有没有可能，环长是 $3$？

答：对于（四连通的）网格图，这是不可能的。把网格图看成国际象棋棋盘，每走一步，所处格子的颜色切换成另一种颜色。对于一个环，从环上的一点出发，只有走偶数步后，所处格子的颜色才和起始格子的颜色相同。所以对于（四连通的）网格图，环长一定是偶数。只要不立刻回头，环长至少为 $4$。

###py

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]

        def dfs(x: int, y: int, px: int, py: int) -> bool:
            vis[x][y] = True
            for i, j in (x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y):  # 枚举移动方向
                if ((i != px or j != py) and  # (i, j) 不是上一步的格子 (px, py)
                    0 <= i < m and 0 <= j < n and  # (i, j) 没有出界
                    grid[i][j] == grid[x][y] and  # (i, j) 和 (x, y) 的格子值相同
                    (vis[i][j] or dfs(i, j, x, y))):  # 如果之前访问过 (i, j)，那么找到了环，否则继续递归找
                    return True
            return False

        for i in range(m):
            for j in range(n):
                if not vis[i][j] and dfs(i, j, -1, -1):
                    return True
        return False

###java

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && dfs(i, j, -1, -1, grid, vis)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int px, int py, char[][] grid, boolean[][] vis) {
        vis[x][y] = true;
        for (int[] d : DIRS) { // 枚举移动方向
            int i = x + d[0];
            int j = y + d[1];
            if ((i != px || j != py) && // (i, j) 不是上一步的格子 (px, py)
                0 <= i && i < grid.length && 0 <= j && j < grid[i].length && // (i, j) 没有出界
                grid[i][j] == grid[x][y] && // (i, j) 和 (x, y) 的格子值相同
                (vis[i][j] || dfs(i, j, x, y, grid, vis))) { // 如果之前访问过 (i, j)，那么找到了环，否则继续递归找
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
    static constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

public:
    bool containsCycle(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector vis(m, vector<int8_t>(n));

        auto dfs = [&](this auto&& dfs, int x, int y, int px, int py) -> bool {
            vis[x][y] = true;
            for (auto [dx, dy] : DIRS) { // 枚举移动方向
                int i = x + dx, j = y + dy;
                if ((i != px || j != py) && // (i, j) 不是上一步的格子 (px, py)
                    0 <= i && i < m && 0 <= j && j < n && // (i, j) 没有出界
                    grid[i][j] == grid[x][y] && // (i, j) 和 (x, y) 的格子值相同
                    (vis[i][j] || dfs(i, j, x, y))) { // 如果之前访问过 (i, j)，那么找到了环，否则继续递归找
                    return true;
                }
            }
            return false;
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && dfs(i, j, -1, -1)) {
                    return true;
                }
            }
        }
        return false;
    }
};

###go

var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下

func containsCycle(grid [][]byte) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}

var dfs func(int, int, int, int) bool
dfs = func(x, y, px, py int) bool {
vis[x][y] = true
for _, d := range dirs { // 枚举移动方向
i, j := x+d.x, y+d.y
if (i != px || j != py) && // (i, j) 不是上一步的格子 (px, py)
0 <= i && i < m && 0 <= j && j < n && // (i, j) 没有出界
grid[i][j] == grid[x][y] && // (i, j) 和 (x, y) 的格子值相同
(vis[i][j] || dfs(i, j, x, y)) { // 如果之前访问过 (i, j)，那么找到了环，否则继续递归找
return true
}
}
return false
}

for i, row := range vis {
for j, b := range row {
if !b && dfs(i, j, -1, -1) {
return true
}
}
}
return false
}

复杂度分析

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

专题训练

见下面网格图题单的「一、网格图 DFS」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

五种方法：二分套二分 / k 指针 / 倍增 / DFS / 动态规划（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年2月23日 12:18

问题转化

最大化最小值，考虑二分答案，即二分距离的下界 $\textit{low}$。为什么？因为 $\textit{low}$ 越大，可以选的点越少，有单调性。

把正方形拉成一条线，示例 2 按照左边界、上边界、右边界、下边界的顺时针顺序，这 $5$ 个点在一维上的坐标为

$$
a=[0,3,4,5,6]
$$

现在问题变成：

能否在数组 $a$ 中选 $k$ 个数，要求任意两个相邻元素相差至少为 $\textit{low}$，且第一个数和最后一个数相差至多为 $\textit{side}\cdot 4 - \textit{low}$。
$\textit{side}\cdot 4 - \textit{low}$ 是因为 $a$ 是个环形数组，设第一个点为 $x$，最后一个点为 $y$，那么 $y$ 可以视作负方向上的 $y-\textit{side}\cdot 4$，我们要求 $x-(y-\textit{side}\cdot 4) \ge \textit{low}$，解得 $y-x\le \textit{side}\cdot 4 - \textit{low}$。

方法一：二分答案 + 二分查找

枚举第一个数，不断向后二分找相距至少为 $\textit{low}$ 的最近元素，直到找到 $k$ 个数，或者第一个数和最后一个数相差超过 $\textit{side}\cdot 4 - \textit{low}$ 时停止。

⚠注意：本题保证 $k\ge 4$，所以答案不会超过 $\textit{side}$。这也保证了如果下一个点不在正方形的当前边或者下一条边上，那么距离是一定满足要求的，所以「二分找下一个点」的做法是正确的。而 $k\le 3$ 时，答案可能会超过 $\textit{side}$，整体没有单调性（比如左边界上的点，到右边界的距离是先变小再变大），需要分段，每段内部是有单调性的，可以每段二分一次。也就是说，$k\le 3$ 的时候，「二分找下一个点」需要多次二分。

⚠注意：不需要找一圈后又绕回到数组 $a$ 的开头继续找。设 $\textit{start}$ 是第一个点，$p$ 是二分找到的最后一个点（绕回到数组开头找到的 $p$）。反证：假设从 $\textit{start}$ 开始搜比从 $p$ 开始搜更优，那么因为我们要求首尾两个点相距 $\ge \textit{low}$，从 $p$ 开始往后搜，下一个点一定是 $\textit{start}$ 或者 $\textit{start}$ 前面的点，所以从 $p$ 开始搜得到的结果，不会比从 $\textit{start}$ 开始搜更差，矛盾。这也同时意味着，无需把环形数组 $a$ 复制一份。

下面代码采用开区间二分，这仅仅是二分的一种写法，使用闭区间或者半闭半开区间都是可以的。

开区间左端点初始值：$1$。一定可以满足要求。
开区间右端点初始值：$\textit{side} + 1$。一定无法满足要求。
开区间右端点初始值（优化）：$\left\lfloor\dfrac{\textit{side}\cdot 4}{k}\right\rfloor + 1$。因为均分周长 $\textit{side}\cdot 4$ 的话，两点相距最小值的最大值是 $\left\lfloor\dfrac{\textit{side}\cdot 4}{k}\right\rfloor$，加一后一定无法满足要求。

答疑

问：为什么需要枚举第一个点是谁？如果从第一个点开始向后二分，没有找到符合要求的 $k$ 个点，那么从第二个点开始向后二分，应该更加不可能找到符合要求的 $k$ 个点呀？

答：比如有 $5$ 个点 $a,b,c,d,e$，我们要选 $k=4$ 个点。假设从 $a$ 开始二分找到的是 $a,c,d,e$，但是点 $a$ 和点 $e$ 太近了。那么继续枚举，假设从 $b$ 开始二分找到的是 $b,c,d,e$，并且 $b$ 和 $e$ 满足要求。这就是一个需要继续枚举的例子，其中 $a$ 离 $b$ 很近，离 $c$ 很远。

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        # 正方形边上的点，按照顺时针映射到一维数轴上
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        def check(low: int) -> bool:
            for start in a:  # 枚举第一个点
                end = start + side * 4 - low
                cur = start
                for _ in range(k - 1):  # 还需要找 k-1 个点
                    j = bisect_left(a, cur + low)
                    if j == len(a) or a[j] > end:  # 不能离第一个点太近
                        break
                    cur = a[j]
                else:
                    return True
            return False

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        # 正方形边上的点，按照顺时针映射到一维数轴上
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        def check(low: int) -> bool:
            # 如果 low+1 不满足要求，但 low 满足要求，那么答案就是 low
            low += 1
            for start in a:  # 枚举第一个点
                end = start + side * 4 - low
                cur = start
                for _ in range(k - 1):  # 还需要找 k-1 个点
                    j = bisect_left(a, cur + low)
                    if j == len(a) or a[j] > end:  # 不能离第一个点太近
                        break
                    cur = a[j]
                else:
                    return False
            return True

        return bisect_left(range(side * 4 // k), True, key=check)

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        // 正方形边上的点，按照顺时针映射到一维数轴上
        long[] a = new long[points.length];
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        Arrays.sort(a);

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int low) {
        next:
        for (long start : a) { // 枚举第一个点
            long end = start + side * 4L - low;
            long cur = start;
            for (int i = 0; i < k - 1; i++) { // 还需要找 k-1 个点
                int j = lowerBound(a, cur + low);
                if (j == a.length || a[j] > end) { // 不能离第一个点太近
                    continue next;
                }
                cur = a[j];
            }
            return true;
        }
        return false;
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(long[] nums, long target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        // 正方形边上的点，按照顺时针映射到一维数轴上
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);

        auto check = [&](int low) -> bool {
            for (long long start : a) { // 枚举第一个点
                long long end = start + side * 4LL - low;
                long long cur = start;
                for (int i = 0; i < k - 1; i++) { // 还需要找 k-1 个点
                    auto it = ranges::lower_bound(a, cur + low);
                    if (it == a.end() || *it > end) { // 不能离第一个点太近
                        cur = -1;
                        break;
                    }
                    cur = *it;
                }
                if (cur >= 0) {
                    return true;
                }
            }
            return false;
        };

        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
// 正方形边上的点，按照顺时针映射到一维数轴上
a := make([]int, len(points))
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)

ans := sort.Search(side*4/k, func(low int) bool {
// 如果 low+1 不满足要求，但 low 满足要求，那么答案就是 low
low++
next:
for i, start := range a { // 枚举第一个点
cur := start
for range k - 1 { // 还需要找 k-1 个点
i += sort.Search(len(a)-i, func(j int) bool { return a[i+j] >= cur+low })
if i == len(a) || a[i] > start+side*4-low { // 不能离第一个点太近
continue next
}
cur = a[i]
}
return false
}
return true
})
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(nk \log \textit{side}\log n)$，其中 $n$ 是 $\textit{points}$ 的长度。由于中途会退出循环，这个复杂度是跑不满的。
空间复杂度：$\mathcal{O}(n)$。

方法二：二分答案 + k 个同向指针

把方法一最内层的二分查找，改用 $k$ 个指针维护。

一开始，初始化一个长为 $k$ 的 $\textit{idx}$ 数组，初始值 $\textit{idx}[j]=0$。

然后写个 $k$ 指针（双指针的推广）：

遍历 $j=1,2,3,\ldots,k-1$，如果发现 $a[\textit{idx}[j]] < a[\textit{idx}[j-1]] + \textit{low}$，就不断把 $\textit{idx}[j]$ 加一直到不满足条件。如果 $\textit{idx}[j]=n$ 则返回。
这些指针移动后，如果首尾两个指针指向的数相差不超过 $\textit{side}\cdot 4 - \textit{low}$，则返回。
否则把 $\textit{idx}[0]$ 加一，继续循环。

优化前

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        def check(low: int) -> bool:
            idx = [0] * k
            while True:
                for j in range(1, k):
                    while a[idx[j]] < a[idx[j - 1]] + low:
                        idx[j] += 1
                        if idx[j] == len(a):
                            return False
                if a[idx[-1]] - a[idx[0]] <= side * 4 - low:
                    return True
                idx[0] += 1

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        long[] a = new long[points.length];
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        Arrays.sort(a);

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int low) {
        int[] idx = new int[k];
        while (true) {
            for (int j = 1; j < k; j++) {
                while (a[idx[j]] < a[idx[j - 1]] + low) {
                    idx[j]++;
                    if (idx[j] == a.length) {
                        return false;
                    }
                }
            }
            if (a[idx[k - 1]] - a[idx[0]] <= side * 4L - low) {
                return true;
            }
            idx[0]++;
        }
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        // 正方形边上的点，按照顺时针映射到一维数轴上
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);

        auto check = [&](int low) -> bool {
            vector<int> idx(k);
            while (true) {
                for (int j = 1; j < k; j++) {
                    while (a[idx[j]] < a[idx[j - 1]] + low) {
                        idx[j]++;
                        if (idx[j] == a.size()) {
                            return false;
                        }
                    }
                }
                if (a[idx[k - 1]] - a[idx[0]] <= side * 4LL - low) {
                    return true;
                }
                idx[0]++;
            }
        };

        // 本题保证 k >= 4，所以最远距离不会超过 side
        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
a := make([]int, len(points))
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)

ans := sort.Search(side*4/k, func(low int) bool {
low++
idx := make([]int, k)
for {
for j := 1; j < k; j++ {
for a[idx[j]] < a[idx[j-1]]+low {
idx[j]++
if idx[j] == len(a) {
return true
}
}
}
if a[idx[k-1]]-a[idx[0]] <= side*4-low {
return false
}
idx[0]++
}
})
return ans
}

优化

把从 $\textit{start}=a[0]$ 开始向后二分得到的 $k$ 个下标，记到 $\textit{idx}$ 数组中。如果没有 $k$ 个下标，直接返回。

这样初始化比从 $0$ 开始一个一个地向后移动指针更快。

此外，第一个指针至多移动到第二个指针的初始位置，就不用继续枚举了，后面必然无法得到符合要求的结果。

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        def check(low: int) -> bool:
            idx = [0] * k
            cur = a[0]
            for j in range(1, k):
                i = bisect_left(a, cur + low)
                if i == len(a):
                    return False
                idx[j] = i
                cur = a[i]
            if cur - a[0] <= side * 4 - low:
                return True

            # 第一个指针移动到第二个指针的位置，就不用继续枚举了
            for idx[0] in range(1, idx[1]):
                for j in range(1, k):
                    while a[idx[j]] < a[idx[j - 1]] + low:
                        idx[j] += 1
                        if idx[j] == len(a):
                            return False
                if a[idx[-1]] - a[idx[0]] <= side * 4 - low:
                    return True
            return False

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        long[] a = new long[points.length];
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        Arrays.sort(a);

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int low) {
        int[] idx = new int[k];
        long cur = a[0];
        for (int j = 1; j < k; j++) {
            int i = lowerBound(a, cur + low);
            if (i == a.length) {
                return false;
            }
            idx[j] = i;
            cur = a[i];
        }
        if (cur - a[0] <= side * 4L - low) {
            return true;
        }

        // 第一个指针移动到第二个指针的位置，就不用继续枚举了
        int end0 = idx[1];
        for (idx[0] = 1; idx[0] < end0; idx[0]++) {
            for (int j = 1; j < k; j++) {
                while (a[idx[j]] < a[idx[j - 1]] + low) {
                    idx[j]++;
                    if (idx[j] == a.length) {
                        return false;
                    }
                }
            }
            if (a[idx[k - 1]] - a[idx[0]] <= side * 4L - low) {
                return true;
            }
        }
        return false;
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(long[] nums, long target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);

        auto check = [&](int low) -> bool {
            vector<int> idx(k);
            long long cur = a[0];
            for (int j = 1; j < k; j++) {
                int i = ranges::lower_bound(a, cur + low) - a.begin();
                if (i == a.size()) {
                    return false;
                }
                idx[j] = i;
                cur = a[i];
            }
            if (cur - a[0] <= side * 4LL - low) {
                return true;
            }

            // 第一个指针移动到第二个指针的位置，就不用继续枚举了
            int end0 = idx[1];
            for (idx[0]++; idx[0] < end0; idx[0]++) {
                for (int j = 1; j < k; j++) {
                    while (a[idx[j]] < a[idx[j - 1]] + low) {
                        idx[j]++;
                        if (idx[j] == a.size()) {
                            return false;
                        }
                    }
                }
                if (a[idx[k - 1]] - a[idx[0]] <= side * 4LL - low) {
                    return true;
                }
            }
            return false;
        };

        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
a := make([]int, len(points))
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)

ans := sort.Search(side*4/k, func(low int) bool {
low++
idx := make([]int, k)
cur := a[0]
for j, i := 1, 0; j < k; j++ {
i += sort.Search(len(a)-i, func(j int) bool { return a[i+j] >= cur+low })
if i == len(a) {
return true
}
idx[j] = i
cur = a[i]
}
if cur-a[0] <= side*4-low {
return false
}

// 第一个指针移动到第二个指针的位置，就不用继续枚举了
end0 := idx[1]
for idx[0]++; idx[0] < end0; idx[0]++ {
for j := 1; j < k; j++ {
for a[idx[j]] < a[idx[j-1]]+low {
idx[j]++
if idx[j] == len(a) {
return true
}
}
}
if a[idx[k-1]]-a[idx[0]] <= side*4-low {
return false
}
}
return true
})
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + nk \log \textit{side})$，其中 $n$ 是 $\textit{points}$ 的长度。其中 $\mathcal{O}(n\log n)$ 是排序的时间复杂度。
空间复杂度：$\mathcal{O}(n)$。

方法三：二分答案 + 倍增

如果 $k$ 更大，上面两个方法就超时了。怎么办？

前置知识：倍增讲解。

在二分中，先预处理 $\textit{nxt}[i][0] = j$ 表示距离 $a[i]$ 至少为 $\textit{low}$ 的下一个点的下标是 $j$。如果不存在则 $j=n$。这可以用双指针计算。

然后倍增，定义 $\textit{nxt}[i][l]$ 表示 $i$ 的下 $2^l$ 个点的下标是 $\textit{nxt}[i][l]$。例如 $\textit{nxt}[i][1]$ 表示 $i$ 的下下个点的下标是 $\textit{nxt}[i][1]$。

转移方程同上面的倍增讲解：

$$
\textit{nxt}[i][l] = \textit{nxt}[\textit{nxt}[i][l-1]][l-1]
$$

可以定义 $\textit{nxt}[n][l]=n$ 作为哨兵，简化代码。

然后枚举 $i=0,1,2,\cdots$，往后跳 $k-1$ 步，得到下标 $j$。如果

$$
a[j] - a[i] \le \textit{side}\cdot 4 - \textit{low}
$$

成立，则说明可以找到符合要求的 $k$ 个点。

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        n = len(a)
        k -= 1  # 往后跳 k-1 步，这里先减一，方便计算
        mx = k.bit_length()
        nxt = [[n] * mx for _ in range(n + 1)]
    
        def check(low: int) -> bool:
            # 预处理倍增数组 nxt
            j = n
            for i in range(n - 1, -1, -1):  # 转移来源在右边，要倒序计算
                while a[j - 1] >= a[i] + low:
                    j -= 1
                nxt[i][0] = j
                for l in range(1, mx):
                    nxt[i][l] = nxt[nxt[i][l - 1]][l - 1]
    
            # 枚举起点
            for i, start in enumerate(a):
                # 往后跳 k-1 步（注意上面把 k 减一了）
                cur = i
                for j in range(mx - 1, -1, -1):
                    if k >> j & 1:
                        cur = nxt[cur][j]
                if cur == n:  # 出界
                    break
                if a[cur] - start <= side * 4 - low:
                    return True
            return False

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        int n = points.length;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        Arrays.sort(a);

        k--; // 往后跳 k-1 步，这里先减一，方便计算
        int mx = 32 - Integer.numberOfLeadingZeros(k);
        int[][] nxt = new int[n + 1][mx];
        Arrays.fill(nxt[n], n); // 哨兵

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, nxt, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int[][] nxt, int low) {
        int n = a.length;
        int mx = nxt[0].length;
        // 预处理倍增数组 nxt
        for (int i = n - 1, j = n; i >= 0; i--) {
            while (a[j - 1] >= a[i] + low) {
                j--;
            }
            nxt[i][0] = j;
            for (int l = 1; l < mx; l++) {
                nxt[i][l] = nxt[nxt[i][l - 1]][l - 1];
            }
        }

        // 枚举起点
        for (int i = 0; i < n; i++) {
            int cur = i;
            // 往后跳 k-1 步（注意上面把 k 减一了）
            for (int j = mx - 1; j >= 0; j--) {
                if ((k >> j & 1) > 0) {
                    cur = nxt[cur][j];
                }
            }
            if (cur == n) { // 出界
                break;
            }
            if (a[cur] - a[i] <= side * 4L - low) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);

        int n = a.size();
        k--; // 往后跳 k-1 步，这里先减一，方便计算
        int high_bit = bit_width((unsigned) k) - 1;
        vector<array<int, 5>> nxt(n + 1); // 5 可以改为 high_bit+1（这里用 array 而不是 vector，提高访问效率）
        ranges::fill(nxt[n], n); // 哨兵

        auto check = [&](int low) -> bool {
            // 预处理倍增数组 nxt
            int j = n;
            for (int i = n - 1; i >= 0; i--) { // 转移来源在右边，要倒序计算
                while (a[j - 1] >= a[i] + low) {
                    j--;
                }
                nxt[i][0] = j;
                for (int k = 1; k <= high_bit; k++) {
                    nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
                }
            }

            // 枚举起点
            for (int i = 0; i < n; i++) {
                int cur = i;
                // 往后跳 k-1 步（注意上面把 k 减一了）
                for (int j = high_bit; j >= 0; j--) {
                    if (k >> j & 1) {
                        cur = nxt[cur][j];
                    }
                }
                if (cur == n) { // 出界
                    break;
                }
                if (a[cur] - a[i] <= side * 4LL - low) {
                    return true;
                }
            }
            return false;
        };

        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
n := len(points)
a := make([]int, n)
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)

k-- // 往后跳 k-1 步，这里先减一，方便计算
highBit := bits.Len(uint(k)) - 1
nxt := make([][5]int, n+1) // 5 可以改为 highBit+1（用 array 而不是 slice，提高访问效率）
for j := range nxt[n] {
nxt[n][j] = n // 哨兵
}

ans := sort.Search(side*4/k, func(low int) bool {
low++
// 预处理倍增数组 nxt
j := n
for i := n - 1; i >= 0; i-- { // 转移来源在右边，要倒序计算
for a[j-1] >= a[i]+low {
j--
}
nxt[i][0] = j
for k := 1; k <= highBit; k++ {
nxt[i][k] = nxt[nxt[i][k-1]][k-1]
}
}

// 枚举起点
for i, start := range a {
// 往后跳 k-1 步（注意上面把 k 减一了）
cur := i
for j := highBit; j >= 0; j-- {
if k>>j&1 > 0 {
cur = nxt[cur][j]
}
}
if cur == n { // 出界
break
}
if a[cur]-start <= side*4-low {
return false
}
}
return true
})
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + n\log k \log \textit{side})$，其中 $n$ 是 $\textit{points}$ 的长度。其中 $\mathcal{O}(n\log n)$ 是排序的时间复杂度。
空间复杂度：$\mathcal{O}(n\log k)$。

方法四：二分答案 + 建树 + DFS

在方法三的双指针基础上，连一条从 $j$ 到 $i$ 的有向边，我们会得到一棵有向树，根是 $n$。

从 $n$ 开始递归这棵树，同时用一个栈记录从根到当前节点的 $a[x]$ 信息。

当栈中有 $k$ 个点时，记录栈中倒数第 $k$ 个数和栈顶的距离，如果 $\le \textit{side}\cdot 4 - \textit{low}$，则找到了满足要求的 $k$ 的点，结束递归。

⚠注意：无需判断 $f[i]>k$ 的情况，因为这意味着之前栈中有 $k$ 个点的时候，首尾两点间的距离足够远（甚至还可以再容纳一个点），一定满足要求。

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()
        n = len(a)
        a.append(inf)  # 哨兵

        def check(low: int) -> bool:
            g = [[] for _ in range(n + 1)]
            j = n
            for i in range(n - 1, -1, -1):
                while a[j - 1] >= a[i] + low:
                    j -= 1
                g[j].append(i)  # 建树

            st = []
            def dfs(x: int) -> bool:
                st.append(a[x])
                # 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
                if len(st) > k and st[-k] - a[x] <= side * 4 - low:
                    return True
                for y in g[x]:
                    if dfs(y):
                        return True
                st.pop()  # 恢复现场
                return False
            return dfs(n)

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        int n = points.length;
        long[] a = new long[n + 1];
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        a[n] = Long.MAX_VALUE; // 哨兵
        Arrays.sort(a);

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int low) {
        int n = a.length - 1;
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = n - 1, j = n; i >= 0; i--) {
            while (a[j - 1] >= a[i] + low) {
                j--;
            }
            g[j].add(i); // 建树
        }

        List<Long> st = new ArrayList<>();
        return dfs(a, g, st, k, side * 4L - low, n);
    }

    private boolean dfs(long[] a, List<Integer>[] g, List<Long> st, int k, long limit, int x) {
        st.add(a[x]);
        int m = st.size();
        // 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
        if (m > k && st.get(m - k) - a[x] <= limit) {
            return true;
        }
        for (int y : g[x]) {
            if (dfs(a, g, st, k, limit, y)) {
                return true;
            }
        }
        st.remove(m - 1); // 恢复现场
        return false;
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);
        int n = a.size();
        a.push_back(LLONG_MAX); // 哨兵

        auto check = [&](int low) -> bool {
            vector<vector<int>> g(n + 1);
            int j = n;
            for (int i = n - 1; i >= 0; i--) {
                while (a[j - 1] >= a[i] + low) {
                    j--;
                }
                g[j].push_back(i); // 建树
            }

            vector<long long> st;
            auto dfs = [&](this auto&& dfs, int x) -> bool {
                st.push_back(a[x]);
                int m = st.size();
                // 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
                if (m > k && st[m - k] - a[x] <= side * 4LL - low) {
                    return true;
                }
                for (int y : g[x]) {
                    if (dfs(y)) {
                        return true;
                    }
                }
                st.pop_back(); // 恢复现场
                return false;
            };
            return dfs(n);
        };

        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
n := len(points)
a := make([]int, n, n+1)
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)
a = append(a, math.MaxInt) // 哨兵

g := make([][]int, n+1)
ans := sort.Search(side*4/k, func(low int) bool {
low++
clear(g)
j := n
for i := n - 1; i >= 0; i-- {
for a[j-1] >= a[i]+low {
j--
}
g[j] = append(g[j], i) // 建树
}

st := []int{}
var dfs func(int) bool
dfs = func(x int) bool {
st = append(st, a[x])
m := len(st)
// 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
if m > k && st[m-k]-a[x] <= side*4-low {
return true
}
for _, y := range g[x] {
if dfs(y) {
return true
}
}
st = st[:m-1] // 恢复现场
return false
}
return !dfs(n)
})
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + n\log \textit{side})$，其中 $n$ 是 $\textit{points}$ 的长度。其中 $\mathcal{O}(n\log n)$ 是排序的时间复杂度。每次二分的时间为 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

方法五：二分 + 动态规划

定义 $f[i]$ 表示从 $i$ 往后找，最多可以找多少个点（包含 $i$）。

设下一个点的下标为 $j$，那么有

$$
f[i] = f[j] + 1
$$

初始值 $f[n] = 0$。

此外，定义 $\textit{end}[i]$ 表示从 $i$ 往后找，最后一个点的下标。

如果 $f[i]=1$，那么 $\textit{end}[i]$ 就是 $i$ 自己。
如果 $f[i]>1$，那么 $\textit{end}[i]$ 是从 $j$ 往后找，最后一个点的下标，即 $\textit{end}[j]$。

所以有

$$
\textit{end}[i] =
\begin{cases}
i, & f[i]=1 \
\textit{end}[j], & f[i]>1 \
\end{cases}
$$

如果 $f[i]=k$，且首尾两点的距离 $a[\textit{end}[i]] - a[i] \le \textit{side}\cdot 4 - \textit{low}$，那么满足要求，返回。

⚠注意：无需判断 $f[i]>k$ 的情况。证明：每次间隔至少 $\textit{low}$ 才会把 $f[i]$ 加 $1$，如果出现 $f[i]=f[j]+1=k+1$ 的情况，说明我们在 $f[j]=k$ 的基础上增加了一个点，对于 $f[j]$ 来说，首尾节点有足够的间距（比 $\textit{low}$ 还大），使得我们可以再加一个点进来，得到 $f[i]=k+1$。所以 $f[j]=k$ 的时候必然可以满足要求，我们不会继续循环到 $f[i]=k+1$ 的情况。

###py

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        a = []
        for x, y in points:
            if x == 0:
                a.append(y)
            elif y == side:
                a.append(side + x)
            elif x == side:
                a.append(side * 3 - y)
            else:
                a.append(side * 4 - x)
        a.sort()

        n = len(a)
        f = [0] * (n + 1)
        end = [0] * n

        def check(low: int) -> bool:
            j = n
            for i in range(n - 1, -1, -1):
                while a[j - 1] >= a[i] + low:
                    j -= 1
                f[i] = f[j] + 1
                end[i] = end[j] if f[i] > 1 else i
                if f[i] == k and a[end[i]] - a[i] <= side * 4 - low:
                    return True
            return False

        left, right = 1, side * 4 // k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

###java

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        int n = points.length;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x == 0) {
                a[i] = y;
            } else if (y == side) {
                a[i] = side + x;
            } else if (x == side) {
                a[i] = side * 3L - y;
            } else {
                a[i] = side * 4L - x;
            }
        }
        Arrays.sort(a);

        int[] f = new int[n + 1];
        int[] end = new int[n];

        int left = 1;
        int right = (int) (side * 4L / k) + 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(a, side, k, mid, f, end)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long[] a, int side, int k, int low, int[] f, int[] end) {
        int n = a.length;
        for (int i = n - 1, j = n; i >= 0; i--) {
            while (a[j - 1] >= a[i] + low) {
                j--;
            }
            f[i] = f[j] + 1;
            end[i] = f[i] > 1 ? end[j] : i;
            if (f[i] == k && a[end[i]] - a[i] <= side * 4L - low) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        vector<long long> a;
        for (auto& p : points) {
            int x = p[0], y = p[1];
            if (x == 0) {
                a.push_back(y);
            } else if (y == side) {
                a.push_back(side + x);
            } else if (x == side) {
                a.push_back(side * 3LL - y);
            } else {
                a.push_back(side * 4LL - x);
            }
        }
        ranges::sort(a);

        int n = a.size();
        vector<int> f(n + 1), end(n);

        auto check = [&](int low) -> bool {
            int j = n;
            for (int i = n - 1; i >= 0; i--) {
                while (a[j - 1] >= a[i] + low) {
                    j--;
                }
                f[i] = f[j] + 1;
                end[i] = f[i] > 1 ? end[j] : i;
                if (f[i] == k && a[end[i]] - a[i] <= side * 4LL - low) {
                    return true;
                }
            }
            return false;
        };

        int left = 1, right = side * 4LL / k + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

###go

func maxDistance(side int, points [][]int, k int) int {
n := len(points)
a := make([]int, n)
for i, p := range points {
x, y := p[0], p[1]
if x == 0 {
a[i] = y
} else if y == side {
a[i] = side + x
} else if x == side {
a[i] = side*3 - y
} else {
a[i] = side*4 - x
}
}
slices.Sort(a)

f := make([]int, n+1)
end := make([]int, n)

ans := sort.Search(side*4/k, func(low int) bool {
low++
j := n
for i := n - 1; i >= 0; i-- {
for a[j-1] >= a[i]+low {
j--
}
f[i] = f[j] + 1
if f[i] == 1 {
end[i] = i // i 自己就是最后一个点
} else {
end[i] = end[j]
}
if f[i] == k && a[end[i]]-a[i] <= side*4-low {
return false
}
}
return true
})
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + n\log \textit{side})$，其中 $n$ 是 $\textit{points}$ 的长度。其中 $\mathcal{O}(n\log n)$ 是排序的时间复杂度。每次二分的时间为 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

贪心（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2023年8月27日 12:15

示例 2 的 $\textit{moves} = \texttt{_R__LL_}$：

先只看 $\texttt{R}$ 和 $\texttt{L}$，往右走了 $1$ 步，再往左走 $2$ 步，相当于往左走了 $1$ 步，位于数轴的 $-1$。
还剩下 $4$ 个 $\texttt{_}$，怎么走最优？当然是继续往左走啦，继续往左走 $4$ 步，最终位于 $-5$。

设 $\textit{cntR}$ 为 $\texttt{R}$ 的个数，$\textit{cntL}$ 为 $\texttt{L}$ 的个数，那么 $\texttt{_}$ 的个数为 $n - \textit{cntR} - \textit{cntL}$。先只看 $\texttt{R}$ 和 $\texttt{L}$，我们到原点的距离为 $|\textit{cntR} - \textit{cntL}|$。然后继续走 $n - \textit{cntR} - \textit{cntL}$ 步，最终答案为

$$
|\textit{cntR} - \textit{cntL}| + n - \textit{cntR} - \textit{cntL}
$$

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        cnt_r = moves.count('R')
        cnt_l = moves.count('L')
        return abs(cnt_r - cnt_l) + len(moves) - cnt_r - cnt_l

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int cntR = 0;
        int cntL = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'R') {
                cntR++;
            } else if (c == 'L') {
                cntL++;
            }
        }
        return Math.abs(cntR - cntL) + moves.length() - cntR - cntL;
    }
}

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int cnt_r = ranges::count(moves, 'R');
        int cnt_l = ranges::count(moves, 'L');
        return abs(cnt_r - cnt_l) + moves.size() - cnt_r - cnt_l;
    }
};

int furthestDistanceFromOrigin(char* moves) {
    int cnt_r = 0;
    int cnt_l = 0;
    int i = 0;
    for (; moves[i]; i++) {
        if (moves[i] == 'R') {
            cnt_r++;
        } else if (moves[i] == 'L') {
            cnt_l++;
        }
    }
    return abs(cnt_r - cnt_l) + i - cnt_r - cnt_l;
}

func furthestDistanceFromOrigin(moves string) int {
cntR := strings.Count(moves, "R")
cntL := strings.Count(moves, "L")
return abs(cntR-cntL) + len(moves) - cntR - cntL
}

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

var furthestDistanceFromOrigin = function(moves) {
    const cntR = [...moves].filter(c => c === 'R').length;
    const cntL = [...moves].filter(c => c === 'L').length;
    return Math.abs(cntR - cntL) + moves.length - cntR - cntL;
};

impl Solution {
    pub fn furthest_distance_from_origin(moves: String) -> i32 {
        let cnt_r = moves.bytes().filter(|&c| c == b'R').count() as i32;
        let cnt_l = moves.bytes().filter(|&c| c == b'L').count() as i32;
        (cnt_r - cnt_l).abs() + moves.len() as i32 - cnt_r - cnt_l
    }
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

两种 O(n) 方法：照搬 2602 / 考虑距离之和的增量

LeetCode 每日一题题解

endlesscheng

2023年4月9日 12:31

本题视频讲解

见【周赛 340】。

方法一：相同元素分组+前缀和

按照相同元素分组后再计算。

这里的思路和 2602. 使数组元素全部相等的最少操作次数（题解）是一样的。由于目标位置就是数组中的下标，无需二分。

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            groups[x].append(i)  # 相同元素分到同一组，记录下标
        ans = [0] * len(nums)
        for a in groups.values():
            n = len(a)
            s = list(accumulate(a, initial=0))  # 前缀和
            for j, target in enumerate(a):
                left = target * j - s[j]  # 蓝色面积
                right = s[n] - s[j] - target * (n - j)  # 绿色面积
                ans[target] = left + right
        return ans

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        var groups = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; ++i) // 相同元素分到同一组，记录下标
            groups.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);

        var ans = new long[n];
        var s = new long[n + 1];
        for (var a : groups.values()) {
            int m = a.size();
            for (int i = 0; i < m; ++i)
                s[i + 1] = s[i] + a.get(i); // 前缀和
            for (int i = 0; i < m; ++i) {
                int target = a.get(i);
                long left = (long) target * i - s[i]; // 蓝色面积
                long right = s[m] - s[i] - (long) target * (m - i); // 绿色面积
                ans[target] = left + right;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[nums[i]].push_back(i); // 相同元素分到同一组，记录下标

        vector<long long> ans(n);
        long long s[n + 1];
        s[0] = 0;
        for (auto& [_, a]: groups) {
            int m = a.size();
            for (int i = 0; i < m; ++i)
                s[i + 1] = s[i] + a[i]; // 前缀和
            for (int i = 0; i < m; ++i) {
                long long target = a[i];
                long long left = target * i - s[i]; // 蓝色面积
                long long right = s[m] - s[i] - target * (m - i); // 绿色面积
                ans[target] = left + right;
            }
        }
        return ans;
    }
};

func distance(nums []int) []int64 {
groups := map[int][]int{}
for i, x := range nums {
groups[x] = append(groups[x], i) // 相同元素分到同一组，记录下标
}
ans := make([]int64, len(nums))
for _, a := range groups {
n := len(a)
s := make([]int, n+1)
for i, x := range a {
s[i+1] = s[i] + x // 前缀和
}
for i, target := range a {
left := target*i - s[i] // 蓝色面积
right := s[n] - s[i] - target*(n-i) // 绿色面积
ans[target] = int64(left + right)
}
}
return ans
}

复杂度分析

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

方法二：相同元素分组+考虑增量

分组后，对于其中一个组 $a$，我们先暴力计算出 $a[0]$ 到其它元素的距离之和，设为 $s_0$。

然后计算 $a[1]$ 到其它元素的距离之和 $s_1$。我们不再暴力计算，而是思考：从 $s_0$ 到 $s_1$，这个增量 $s_1-s_0$ 是多少？（增量可以是负数）

设 $n$ 为 $a$ 的长度，从 $s_0$ 到 $s_1$，有 $1$ 个数的距离变大了 $a[1]-a[0]$（原来是到 $a[0]$ 的距离，现在是到 $a[1]$ 的距离；原来是 $a[0]$ 到 $a[0]$ 的距离为 $0$，现在是 $a[0]$ 到 $a[1]$ 的距离为 $a[1]-a[0]$），其余 $n-1$ 个数的距离变小了 $a[1]-a[0]$（原来是到 $a[0]$ 的距离，现在是到 $a[1]$ 的距离）。

所以对于 $s_1$，我们可以 $\mathcal{O}(1)$ 地知道 $a[1]$ 到其它元素的距离之和为

$$
s_0 + (2-n) \cdot (a[1]-a[0])
$$

一般地，设 $a[i-1]$ 到其它元素的距离之和为 $s$，那么 $a[i]$ 到其它元素的距离之和为

$$
s + (2i-n) \cdot (a[i]-a[i-1])
$$

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            groups[x].append(i)  # 相同元素分到同一组，记录下标
        ans = [0] * len(nums)
        for a in groups.values():
            n = len(a)
            s = sum(x - a[0] for x in a)  # a[0] 到其它下标的距离之和
            ans[a[0]] = s
            for i in range(1, n):
                # 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                s += (i * 2 - n) * (a[i] - a[i - 1])
                ans[a[i]] = s
        return ans

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        var groups = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; ++i) // 相同元素分到同一组，记录下标
            groups.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);

        var ans = new long[n];
        for (var a : groups.values()) {
            int m = a.size();
            long s = 0;
            for (int x : a)
                s += x - a.get(0); // a[0] 到其它下标的距离之和
            ans[a.get(0)] = s;
            for (int i = 1; i < m; ++i)
                // 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                ans[a.get(i)] = s += (long) (i * 2 - m) * (a.get(i) - a.get(i - 1));
        }
        return ans;
    }
}

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[nums[i]].push_back(i); // 相同元素分到同一组，记录下标

        vector<long long> ans(n);
        for (auto& [_, a]: groups) {
            int m = a.size();
            long long s = 0;
            for (int x: a)
                s += x - a[0]; // a[0] 到其它下标的距离之和
            ans[a[0]] = s;
            for (int i = 1; i < m; ++i)
                // 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                ans[a[i]] = s += (long long) (i * 2 - m) * (a[i] - a[i - 1]);
        }
        return ans;
    }
};

func distance(nums []int) []int64 {
groups := map[int][]int{}
for i, x := range nums {
groups[x] = append(groups[x], i) // 相同元素分到同一组，记录下标
}
ans := make([]int64, len(nums))
for _, a := range groups {
n := len(a)
s := int64(0)
for _, x := range a {
s += int64(x - a[0]) // a[0] 到其它下标的距离之和
}
ans[a[0]] = s
for i := 1; i < n; i++ {
// 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
s += int64(i*2-n) * int64(a[i]-a[i-1])
ans[a[i]] = s
}
}
return ans
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

暴力（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

endlesscheng

2022年10月30日 07:58

对于每个 $q = \textit{queries}[i]$，遍历 $\textit{dictionary}$ 中的字符串 $s$，判断 $q$ 和 $s$ 是否至多有两个位置上的字母不同。

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for q in queries:
            for s in dictionary:
                if sum(x != y for x, y in zip(q, s)) <= 2:
                    ans.append(q)
                    break
        return ans

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> ans = new ArrayList<>();
        for (String q : queries) {
            for (String s : dictionary) {
                int cnt = 0;
                for (int i = 0; i < s.length() && cnt <= 2; i++) {
                    if (q.charAt(i) != s.charAt(i)) {
                        cnt++;
                    }
                }
                if (cnt <= 2) {
                    ans.add(q);
                    break;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for (auto& q : queries) {
            for (auto& s : dictionary) {
                int cnt = 0;
                for (int i = 0; i < s.size() && cnt <= 2; i++) {
                    if (q[i] != s[i]) {
                        cnt++;
                    }
                }
                if (cnt <= 2) {
                    ans.push_back(q);
                    break;
                }
            }
        }
        return ans;
    }
};

char** twoEditWords(char** queries, int queriesSize, char** dictionary, int dictionarySize, int* returnSize) {
    char** ans = malloc(queriesSize * sizeof(char*));
    *returnSize = 0;

    for (int i = 0; i < queriesSize; i++) {
        char* q = queries[i];
        for (int j = 0; j < dictionarySize; j++) {
            char* s = dictionary[j];
            int cnt = 0;
            for (int k = 0; s[k] && cnt <= 2; k++) {
                if (q[k] != s[k]) {
                    cnt++;
                }
            }
            if (cnt <= 2) {
                ans[(*returnSize)++] = q;
                break;
            }
        }
    }

    return ans;
}

func twoEditWords(queries, dictionary []string) (ans []string) {
for _, q := range queries {
next:
for _, s := range dictionary {
cnt := 0
for i := range s {
if q[i] != s[i] {
cnt++
if cnt > 2 {
continue next
}
}
}
ans = append(ans, q)
break
}
}
return
}

var twoEditWords = function(queries, dictionary) {
    const ans = [];
    for (const q of queries) {
        for (const s of dictionary) {
            let cnt = 0;
            for (let i = 0; i < s.length && cnt <= 2; i++) {
                if (q[i] !== s[i]) {
                    cnt++;
                }
            }
            if (cnt <= 2) {
                ans.push(q);
                break;
            }
        }
    }
    return ans;
};

impl Solution {
    pub fn two_edit_words(queries: Vec<String>, dictionary: Vec<String>) -> Vec<String> {
        let mut ans = vec![];
        for q in queries {
            for s in &dictionary {
                let mut cnt = 0;
                for (a, b) in q.bytes().zip(s.bytes()) {
                    if a != b {
                        cnt += 1;
                        if cnt > 2 {
                            break;
                        }
                    }
                }
                if cnt <= 2 {
                    ans.push(q);
                    break;
                }
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(qdn)$，其中 $q$ 是 $\textit{queries}$ 的长度，$d$ 是 $\textit{dictionary}$ 的长度，$n$ 是 $\textit{queries}[i]$ 的长度。题目保证所有字符串长度相等。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

阅读视图

一、寻找子问题

二、状态定义与状态转移方程

三、递归搜索 + 保存递归返回值 = 记忆化搜索

复杂度分析

四、1:1 翻译成递推

复杂度分析

五、值域线段树优化 DP

复杂度分析

相似题目

分类题单

复杂度分析

空间优化

复杂度分析

分类题单

方法一：正向思维

复杂度分析

方法二：逆向思维

复杂度分析

相似题目

分类题单

复杂度分析

分类题单

方法一：正序遍历

复杂度分析

方法二：倒序遍历 + 双指针

复杂度分析

专题训练

分类题单

复杂度分析

分类题单

题意

分析

两次翻转等于一次旋转

实现

写法一

写法二

复杂度分析

思考题

相似题目

分类题单

方法一：暴力

复杂度分析

方法二：字符串匹配

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

相似题目

分类题单

记忆化搜索

递推

复杂度分析

空间优化

复杂度分析

优化循环次数

复杂度分析

专题训练

分类题单

一、从超时做法说起

复杂度分析（超时）

二、记忆化搜索

复杂度分析

三、1:1 翻译成递推

复杂度分析

四、时间优化

1) pre > 0 且 dec = 1

2) pre > 0 且 dec = 0

3) pre = 0 且 dec = 0

4) pre = 0 且 dec = 1

复杂度分析

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

专题训练