一、从超时做法说起

从 $\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 的过程中计算列的前缀和。

分类题单

如何科学刷题？

1. 滑动窗口（定长/不定长/多指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）

我的题解精选（已分类）

先判断是否无解。

例如 $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 中位数贪心」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

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

1. 站在 $(x,y)$，下一步可以往哪些方向移动？
2. 如何判断相邻街道是否连通？示例 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」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

在 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」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

问题转化

最大化最小值，考虑二分答案，即二分距离的下界 $\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)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 【本题相关】二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

示例 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)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

本题视频讲解

见【周赛 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)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

对于每个 $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)$。返回值不计入。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

在 $a_i$ 和 $b_i$ 之间连边，得到一个无向图 $G$。

$G$ 的同一个连通块中的节点（下标）可以随意交换。

证明（具体交换方案）

例如 $\textit{source}$ 在某个连通块中的元素为 $1,1,2,3$，$\textit{target}$ 在这个连通块中的元素为 $2,2,4,1$，二者有一个共同的 $1$ 和一个共同的 $2$。但 $\textit{source}$ 多了一个 $1$ 和一个 $3$，$\textit{target}$ 多了一个 $2$ 和一个 $4$，每对多出来的元素，无法匹配，会贡献 $1$ 个汉明距离。所以这个连通块贡献了 $2$ 个汉明距离。

用哈希表（或者数组）统计 $\textit{source}$ 和 $\textit{target}$ 各自多出来的元素个数。总个数除以 $2$，即为无法配对的元素对的个数，即汉明距离。

###py

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        g = [[] for _ in range(n)]
        for i, j in allowedSwaps:
            g[i].append(j)  # 建图
            g[j].append(i)

        def dfs(x: int) -> None:
            vis[x] = True  # 避免重复访问
            # 抵消相同的元素，最终剩下 source 和 target 各自多出来的元素（对称差）
            diff[source[x]] += 1
            diff[target[x]] -= 1
            for y in g[x]:
                if not vis[y]:
                    dfs(y)

        vis = [False] * n
        ans = 0
        for x in range(n):
            if not vis[x]:
                diff = defaultdict(int)
                dfs(x)
                ans += sum(map(abs, diff.values()))
        return ans // 2  # 有 ans // 2 对多出来的元素

###java

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : allowedSwaps) {
            int i = e[0];
            int j = e[1];
            g[i].add(j); // 建图
            g[j].add(i);
        }

        boolean[] vis = new boolean[n];
        int ans = 0;
        for (int x = 0; x < n; x++) {
            if (!vis[x]) {
                Map<Integer, Integer> diff = new HashMap<>();
                dfs(x, source, target, g, vis, diff);
                for (int c : diff.values()) {
                    ans += Math.abs(c);
                }
            }
        }
        return ans / 2; // 有 ans / 2 对多出来的元素
    }

    private void dfs(int x, int[] source, int[] target, List<Integer>[] g, boolean[] vis, Map<Integer, Integer> diff) {
        vis[x] = true; // 避免重复访问
        // 抵消相同的元素，最终剩下 source 和 target 各自多出来的元素（对称差）
        diff.merge(source[x], 1, Integer::sum);  // diff[source[x]]++;
        diff.merge(target[x], -1, Integer::sum); // diff[target[x]]--;
        for (int y : g[x]) {
            if (!vis[y]) {
                dfs(y, source, target, g, vis, diff);
            }
        }
    }
}

###cpp

class Solution {
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        vector<vector<int>> g(n);
        for (auto& e : allowedSwaps) {
            int i = e[0], j = e[1];
            g[i].push_back(j); // 建图
            g[j].push_back(i);
        }

        vector<int8_t> vis(n);
        unordered_map<int, int> diff;

        auto dfs = [&](this auto&& dfs, int x) -> void {
            vis[x] = true; // 避免重复访问
            // 抵消相同的元素，最终剩下 source 和 target 各自多出来的元素（对称差）
            diff[source[x]]++;
            diff[target[x]]--;
            for (int y : g[x]) {
                if (!vis[y]) {
                    dfs(y);
                }
            }
        };

        int ans = 0;
        for (int x = 0; x < n; x++) {
            if (!vis[x]) {
                diff.clear();
                dfs(x);
                for (auto& [_, c] : diff) {
                    ans += abs(c);
                }
            }
        }
        return ans / 2; // 有 ans / 2 对多出来的元素
    }
};

###go

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) (ans int) {
n := len(source)
g := make([][]int, n)
for _, e := range allowedSwaps {
i, j := e[0], e[1]
g[i] = append(g[i], j) // 建图
g[j] = append(g[j], i)
}

vis := make([]bool, n)
diff := map[int]int{}

var dfs func(int)
dfs = func(x int) {
vis[x] = true // 避免重复访问
// 抵消相同的元素，最终剩下 source 和 target 各自多出来的元素（对称差）
diff[source[x]]++
diff[target[x]]--
for _, y := range g[x] {
if !vis[y] {
dfs(y)
}
}
}

for x, b := range vis {
if !b {
clear(diff)
dfs(x)
for _, c := range diff {
ans += abs(c)
}
}
}
return ans / 2 // 有 ans / 2 对多出来的元素
}

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

复杂度分析

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

相似题目

• 1202. 交换字符串中的元素
• 1722. 执行交换操作后的最小汉明距离
• 3695. 交换元素后的最大交替和

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

如果 $\textit{colors}[0] \ne \textit{colors}[n-1]$，那么答案是 $n-1$。

否则设 $c = \textit{colors}[0] = \textit{colors}[n-1]$。

设最大距离来自房子 $i$ 和房子 $j$。由于题目要求 $\textit{colors}[i]\ne \textit{colors}[j]$，所以这两个颜色不可能都等于 $c$。如果 $\textit{colors}[i]\ne c$，那么 $j$ 必然是离 $i$ 最远的 $0$ 或者 $n-1$（这两栋房子的颜色与房子 $i$ 不同）。这意味着，$0$ 或者 $n-1$ 必然参与最大距离的计算。

• 对于房子 $0$ 来说，另一栋房子越远（越靠右）越好。从右往左找到颜色不等于 $c$ 的房子 $\textit{colors}[r]$，距离为 $r-0 = r$。
• 对于房子 $n-1$ 来说，另一栋房子越远（越靠左）越好。从左往右找到颜色不等于 $c$ 的房子 $\textit{colors}[\ell]$，距离为 $n-1-\ell$。

答案为二者的最大值

$$
\max(r, n-1-\ell)
$$

注意题目保证至少有两栋颜色不同的房子。

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        c = colors[0]
        if c != colors[-1]:
            return n - 1

        # 找最右边的颜色不等于 c 的房子
        # 题目保证至少有两栋颜色不同的房子
        r = n - 2
        while colors[r] == c:
            r -= 1

        # 找最左边的颜色不等于 c 的房子
        l = 1
        while colors[l] == c:
            l += 1

        return max(r, n - 1 - l)

class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int c = colors[0];
        if (c != colors[n - 1]) {
            return n - 1;
        }

        // 找最右边的颜色不等于 c 的房子
        // 题目保证至少有两栋颜色不同的房子
        int r = n - 2;
        while (colors[r] == c) {
            r--;
        }

        // 找最左边的颜色不等于 c 的房子
        int l = 1;
        while (colors[l] == c) {
            l++;
        }

        return Math.max(r, n - 1 - l);
    }
}

class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int n = colors.size();
        int c = colors[0];
        if (c != colors[n - 1]) {
            return n - 1;
        }

        // 找最右边的颜色不等于 c 的房子
        // 题目保证至少有两栋颜色不同的房子
        int r = n - 2;
        while (colors[r] == c) {
            r--;
        }

        // 找最左边的颜色不等于 c 的房子
        int l = 1;
        while (colors[l] == c) {
            l++;
        }

        return max(r, n - 1 - l);
    }
};

int maxDistance(int* colors, int colorsSize) {
    int n = colorsSize;
    int c = colors[0];
    if (c != colors[n - 1]) {
        return n - 1;
    }

    // 找最右边的颜色不等于 c 的房子
    // 题目保证至少有两栋颜色不同的房子
    int r = n - 2;
    while (colors[r] == c) {
        r--;
    }

    // 找最左边的颜色不等于 c 的房子
    int l = 1;
    while (colors[l] == c) {
        l++;
    }

    return MAX(r, n - 1 - l);
}

func maxDistance(colors []int) int {
n := len(colors)
c := colors[0]
if c != colors[n-1] {
return n - 1
}

// 找最右边的颜色不等于 c 的房子
// 题目保证至少有两栋颜色不同的房子
r := n - 2
for colors[r] == c {
r--
}

// 找最左边的颜色不等于 c 的房子
l := 1
for colors[l] == c {
l++
}

return max(r, n-1-l)
}

var maxDistance = function(colors) {
    const n = colors.length;
    const c = colors[0];
    if (c !== colors[n - 1]) {
        return n - 1;
    }

    // 找最右边的颜色不等于 c 的房子
    // 题目保证至少有两栋颜色不同的房子
    let r = n - 2;
    while (colors[r] === c) {
        r--;
    }

    // 找最左边的颜色不等于 c 的房子
    let l = 1;
    while (colors[l] === c) {
        l++;
    }

    return Math.max(r, n - 1 - l);
};

impl Solution {
    pub fn max_distance(colors: Vec<i32>) -> i32 {
        let n = colors.len();
        let c = colors[0];
        if c != colors[n - 1] {
            return (n - 1) as _;
        }

        // 找最右边的颜色不等于 c 的房子
        // 题目保证至少有两栋颜色不同的房子
        let mut r = n - 2;
        while colors[r] == c {
            r -= 1;
        }

        // 找最左边的颜色不等于 c 的房子
        let mut l = 1;
        while colors[l] == c {
            l += 1;
        }

        r.max(n - 1 - l) as _
    }
}

复杂度分析

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

专题训练

见下面贪心与思维题单的「§5.2 脑筋急转弯」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

枚举 $j$，随着 $j$ 的变大，$\textit{nums}_2[j]$ 变小，满足要求的最小的 $i$ 随之变大。

所以可以用双指针做：如果 $j$ 变大后，发现 $\textit{nums}_1[i] > \textit{nums}_2[j]$，那么增大 $i$，直到 $i=n$ 或者 $\textit{nums}_1 \le \textit{nums}_2[j]$ 为止。然后用 $j-i$ 更新答案的最大值（答案初始为 $0$）。

无需担心 $j-i < 0$，这不会影响答案。

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        ans = i = 0
        for j, y in enumerate(nums2):
            while i < len(nums1) and nums1[i] > y:
                i += 1
            if i == len(nums1):
                break
            ans = max(ans, j - i)
        return ans

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums2.length; j++) {
            while (i < nums1.length && nums1[i] > nums2[j]) {
                i++;
            }
            if (i == nums1.length) {
                break;
            }
            ans = Math.max(ans, j - i);
        }
        return ans;
    }
}

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums2.size(); j++) {
            while (i < nums1.size() && nums1[i] > nums2[j]) {
                i++;
            }
            if (i == nums1.size()) {
                break;
            }
            ans = max(ans, j - i);
        }
        return ans;
    }
};

int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int ans = 0;
    int i = 0;
    for (int j = 0; j < nums2Size; j++) {
        int y = nums2[j];
        while (i < nums1Size && nums1[i] > y) {
            i++;
        }
        if (i == nums1Size) {
            break;
        }
        ans = MAX(ans, j - i);
    }
    return ans;
}

func maxDistance(nums1, nums2 []int) (ans int) {
i := 0
for j, y := range nums2 {
for i < len(nums1) && nums1[i] > y {
i++
}
if i == len(nums1) {
break
}
ans = max(ans, j-i)
}
return
}

var maxDistance = function(nums1, nums2) {
    let ans = 0;
    let i = 0;
    for (let j = 0; j < nums2.length; j++) {
        while (i < nums1.length && nums1[i] > nums2[j]) {
            i++;
        }
        if (i === nums1.length) {
            break;
        }
        ans = Math.max(ans, j - i);
    }
    return ans;
};

impl Solution {
    pub fn max_distance(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut i = 0;
        for (j, y) in nums2.into_iter().enumerate() {
            while i < nums1.len() && nums1[i] > y {
                i += 1;
            }
            if i == nums1.len() {
                break;
            }
            ans = ans.max(j as i32 - i as i32);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+m)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。虽然我们写了个二重循环，但 $i$ 最多自增 $n$ 次，所以二重循环的循环次数至多为 $n+m$。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面双指针题单的「四、双序列双指针」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

不断地把 $n$ 除以 $10$（下取整）直到 $0$，例如 $123\to 12\to 1\to 0$。在这个过程中的 $d = n\bmod 10$，即为每个数位。

计算 $\textit{rev} \cdot 10 + d$，可以把数字 $d$ 添加到 $\textit{rev}$ 的末尾。例如 $32\cdot 10 + 1 = 321$。

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

###py

class Solution:
    def mirrorDistance(self, n: int) -> int:
        rev = int(str(n)[::-1])
        return abs(n - rev)

###py

class Solution:
    def mirrorDistance(self, n: int) -> int:
        rev = 0
        x = n
        while x > 0:
            x, d = divmod(x, 10)
            rev = rev * 10 + d
        return abs(n - rev)

###java

class Solution {
    public int mirrorDistance(int n) {
        int rev = 0;
        for (int x = n; x > 0; x /= 10) {
            rev = rev * 10 + x % 10;
        }
        return Math.abs(n - rev);
    }
}

###cpp

class Solution {
public:
    int mirrorDistance(int n) {
        int rev = 0;
        for (int x = n; x > 0; x /= 10) {
            rev = rev * 10 + x % 10;
        }
        return abs(n - rev);
    }
};

###go

func mirrorDistance(n int) int {
rev := 0
for x := n; x > 0; x /= 10 {
rev = rev*10 + x%10
}
return abs(n - rev)
}

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

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$。循环次数等于 $n$ 的十进制长度 $\mathcal{O}(\log n)$。
• 空间复杂度：$\mathcal{O}(\log n)$ 或 $\mathcal{O}(1)$，取决于是否使用字符串。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

枚举 $j$，同时用哈希表维护 $j$ 左边的 $\text{reverse}(\textit{nums}[i])$ 的最大下标，哈希表的 key 是 $\text{reverse}(\textit{nums}[i])$，value 是下标 $i$。

如果哈希表中有 $\textit{nums}[j]$，获取对应的下标 $i$，用 $j-i$ 更新答案的最小值。

⚠注意：请仔细读题，题目要求的是 reverse(nums[i]) == nums[j]，不是 reverse(nums[j]) == nums[i]，下标必须满足 $i<j$，不是对称的。

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

###py

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        last_index = {}
        ans = inf

        for j, x in enumerate(nums):
            if x in last_index:
                ans = min(ans, j - last_index[x])
            rev = int(str(x)[::-1])
            last_index[rev] = j

        return ans if ans < inf else -1

###py

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        last_index = {}
        ans = inf

        for j, x in enumerate(nums):
            if x in last_index:
                ans = min(ans, j - last_index[x])

            # 计算 reverse(x)，不用字符串
            rev = 0
            while x > 0:
                x, d = divmod(x, 10)
                rev = rev * 10 + d
            last_index[rev] = j

        return ans if ans < inf else -1

###java

class Solution {
    public int minMirrorPairDistance(int[] nums) {
        int n = nums.length;
        int ans = n;
        Map<Integer, Integer> lastIndex = new HashMap<>(n, 1); // 预分配空间

        for (int j = 0; j < n; j++) {
            int x = nums[j];
            Integer i = lastIndex.get(x);
            if (i != null) {
                ans = Math.min(ans, j - i);
            }

            // 计算 reverse(x)，不用字符串
            int rev = 0;
            for (; x > 0; x /= 10) {
                rev = rev * 10 + x % 10;
            }
            lastIndex.put(rev, j);
        }

        return ans < n ? ans : -1;
    }
}

###cpp

class Solution {
public:
    int minMirrorPairDistance(vector<int>& nums) {
        unordered_map<int, int> last_index;
        int n = nums.size(), ans = n;

        for (int j = 0; j < n; j++) {
            int x = nums[j];
            auto it = last_index.find(x);
            if (it != last_index.end()) {
                ans = min(ans, j - it->second);
            }

            // 计算 reverse(x)，不用字符串
            int rev = 0;
            for (; x > 0; x /= 10) {
                rev = rev * 10 + x % 10;
            }
            last_index[rev] = j;
        }

        return ans < n ? ans : -1;
    }
};

###go

func minMirrorPairDistance(nums []int) int {
n := len(nums)
ans := n
lastIndex := make(map[int]int, n) // 预分配空间

for j, x := range nums {
if i, ok := lastIndex[x]; ok {
ans = min(ans, j-i)
}

// 计算 reverse(x)，不用字符串
rev := 0
for ; x > 0; x /= 10 {
rev = rev*10 + x%10
}
lastIndex[rev] = j
}

if ans == n {
return -1
}
return ans
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是 $\textit{nums}$ 的长度，$U=\max(\textit{nums})$。反转一个数字需要 $\mathcal{O}(\log U)$ 时间。
• 空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面数据结构题单的「§0.1 枚举右，维护左」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

方法一：二分查找

看示例 1，所有 $1$ 的下标列表是 $p=[0,2,4]$。

我们在 $p$ 中二分查找下标 $i$，设二分返回值为 $j$，那么：

• $p[j-1]$ 就是在 $i$ 左边的最近位置。
• $p[j+1]$ 就是在 $i$ 右边的最近位置。

两个距离取最小值，答案为

$$
\min(i-p[j-1], p[j+1]-i)
$$

如果 $j-1$ 或者 $j+1$ 下标越界怎么办？需要写一堆 $\texttt{if-else}$ 吗？

在示例 1 中，由于 $\textit{nums}$ 是循环数组：

• 在下标列表前面添加 $4-n=-3$，相当于认为在 $-3$ 下标处也有一个 $1$。
• 在下标列表末尾添加 $0+n=7$，相当于认为在 $7$ 下标处也有一个 $1$。

修改后的下标列表为 $p=[-3,0,2,4,7]$。

特别地，如果 $\textit{nums}[i]$ 在 $\textit{nums}$ 中只出现了一次，那么答案为 $-1$。

代码实现时，可以直接把答案记录在 $\textit{queries}$ 数组中。

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

###py

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        indices = defaultdict(list)
        for i, x in enumerate(nums):
            indices[x].append(i)

        n = len(nums)
        for p in indices.values():
            # 前后各加一个哨兵
            i0 = p[0]
            p.insert(0, p[-1] - n)
            p.append(i0 + n)

        for qi, i in enumerate(queries):
            p = indices[nums[i]]
            if len(p) == 3:
                queries[qi] = -1
            else:
                j = bisect_left(p, i)
                queries[qi] = min(i - p[j - 1], p[j + 1] - i)
        return queries

###java

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            indices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int n = nums.length;
        for (List<Integer> p : indices.values()) {
            // 前后各加一个哨兵
            int i0 = p.get(0);
            p.add(0, p.get(p.size() - 1) - n);
            p.add(i0 + n);
        }

        List<Integer> ans = new ArrayList<>(queries.length); // 预分配空间
        for (int i : queries) {
            List<Integer> p = indices.get(nums[i]);
            if (p.size() == 3) {
                ans.add(-1);
            } else {
                int j = Collections.binarySearch(p, i);
                ans.add(Math.min(i - p.get(j - 1), p.get(j + 1) - i));
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        unordered_map<int, vector<int>> indices;
        for (int i = 0; i < nums.size(); i++) {
            indices[nums[i]].push_back(i);
        }

        int n = nums.size();
        for (auto& [_, p] : indices) {
            // 前后各加一个哨兵
            int i0 = p[0];
            p.insert(p.begin(), p.back() - n);
            p.push_back(i0 + n);
        }

        for (int& i : queries) { // 注意这里是引用
            auto& p = indices[nums[i]];
            if (p.size() == 3) {
                i = -1;
            } else {
                int j = ranges::lower_bound(p, i) - p.begin();
                i = min(i - p[j - 1], p[j + 1] - i);
            }
        }
        return queries;
    }
};

###go

func solveQueries(nums []int, queries []int) []int {
indices := map[int][]int{}
for i, x := range nums {
indices[x] = append(indices[x], i)
}

n := len(nums)
for x, p := range indices {
// 前后各加一个哨兵
i0 := p[0]
p = slices.Insert(p, 0, p[len(p)-1]-n)
indices[x] = append(p, i0+n)
}

for qi, i := range queries {
p := indices[nums[i]]
if len(p) == 3 {
queries[qi] = -1
} else {
j := sort.SearchInts(p, i)
queries[qi] = min(i-p[j-1], p[j+1]-i)
}
}
return queries
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n + q\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度，$q$ 是 $\textit{queries}$ 的长度。每次二分需要 $\mathcal{O}(\log n)$ 的时间。
• 空间复杂度：$\mathcal{O}(n)$。返回值不计入。

方法二：预处理左右最近相同元素的下标

定义 $\textit{left}[i]$ 表示在 $i$ 左边的等于 $\textit{nums}[i]$ 的最近元素下标。注意数组是循环数组，我们可以像方法一那样，用 $-1$ 表示最后一个数的下标，$-2$ 表示倒数第二个数的下标，依此类推。

定义 $\textit{right}[i]$ 表示在 $i$ 右边的等于 $\textit{nums}[i]$ 的最近元素下标。注意数组是循环数组，我们可以像方法一那样，用 $n$ 表示第一个数的下标，$n+1$ 表示第二个数的下标，依此类推。

计算方式：

• 从 $-n$ 循环到 $n-1$，同时用一个哈希表记录每个数的最新位置。当 $i\ge 0$ 时，$\textit{left}[i]$ 就是哈希中记录的 $\textit{nums}[i]$ 的位置。注意先更新 $\textit{left}[i]$ 再更新哈希表。
• 从 $2n-1$ 循环到 $0$，同时用一个哈希表记录每个数的最新位置。当 $i < n$ 时，$\textit{right}[i]$ 就是哈希中记录的 $\textit{nums}[i]$ 的位置。注意先更新 $\textit{right}[i]$ 再更新哈希表。

答案为：

$$
\min(i-\textit{left}[i], \textit{right}[i]-i)
$$

如果上式等于 $n$，说明只有一个 $\textit{nums}[i]$，答案为 $-1$。

优化前

###py

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        left = [0] * n
        pos = {}
        for i in range(-n, n):
            if i >= 0:
                left[i] = pos[nums[i]]
            pos[nums[i]] = i

        right = [0] * n
        pos.clear()
        for i in range(n * 2 - 1, -1, -1):
            if i < n:
                right[i] = pos[nums[i]]
            pos[nums[i % n]] = i

        for qi, i in enumerate(queries):
            l = left[i]
            queries[qi] = -1 if i - l == n else min(i - l, right[i] - i)
        return queries

###java

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int[] left = new int[n];
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = -n; i < n; i++) {
            if (i >= 0) {
                left[i] = pos.get(nums[i]);
            }
            pos.put(nums[(i + n) % n], i);
        }

        int[] right = new int[n];
        pos.clear();
        for (int i = n * 2 - 1; i >= 0; i--) {
            if (i < n) {
                right[i] = pos.get(nums[i]);
            }
            pos.put(nums[i % n], i);
        }

        List<Integer> ans = new ArrayList<>(queries.length);
        for (int i : queries) {
            int l = left[i];
            ans.add(i - l == n ? -1 : Math.min(i - l, right[i] - i));
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        vector<int> left(n), right(n);
        unordered_map<int, int> pos;
        for (int i = -n; i < n; i++) {
            if (i >= 0) {
                left[i] = pos[nums[i]];
            }
            pos[nums[(i + n) % n]] = i;
        }

        pos.clear();
        for (int i = n * 2 - 1; i >= 0; i--) {
            if (i < n) {
                right[i] = pos[nums[i]];
            }
            pos[nums[i % n]] = i;
        }

        for (int& i : queries) {
            int l = left[i];
            i = i - l == n ? -1 : min(i - l, right[i] - i);
        }
        return queries;
    }
};

###go

func solveQueries(nums []int, queries []int) []int {
n := len(nums)
left := make([]int, n)
pos := map[int]int{}
for i := -n; i < n; i++ {
if i >= 0 {
left[i] = pos[nums[i]]
}
pos[nums[(i+n)%n]] = i
}

right := make([]int, n)
clear(pos)
for i := n*2 - 1; i >= 0; i-- {
if i < n {
right[i] = pos[nums[i]]
}
pos[nums[i%n]] = i
}

for qi, i := range queries {
l := left[i]
if i-l == n {
queries[qi] = -1
} else {
queries[qi] = min(i-l, right[i]-i)
}
}
return queries
}

优化（一）

一次遍历同时计算 $\textit{left}$ 和 $\textit{right}$。（类似单调栈）

###py

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        left = [0] * n
        right = [0] * n
        pos = {}
        for i in range(-n, n):
            x = nums[i]
            if i >= 0:
                j = pos[x]
                left[i] = j
                # 对于左边的 j 来说，它的 right 就是 i
                if j >= 0:
                    right[j] = i
                else:
                    right[j + n] = i + n
            pos[x] = i

        for qi, i in enumerate(queries):
            l = left[i]
            queries[qi] = -1 if i - l == n else min(i - l, right[i] - i)
        return queries

###java

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = -n; i < n; i++) {
            if (i >= 0) {
                int j = pos.get(nums[i]);
                left[i] = j;
                // 对于左边的 j 来说，它的 right 就是 i
                if (j >= 0) {
                    right[j] = i;
                } else {
                    right[j + n] = i + n;
                }
            }
            pos.put(nums[(i + n) % n], i);
        }

        List<Integer> ans = new ArrayList<>(queries.length);
        for (int i : queries) {
            int l = left[i];
            ans.add(i - l == n ? -1 : Math.min(i - l, right[i] - i));
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        vector<int> left(n), right(n);
        unordered_map<int, int> pos;
        for (int i = -n; i < n; i++) {
            if (i >= 0) {
                int j = pos[nums[i]];
                left[i] = j;
                // 对于左边的 j 来说，它的 right 就是 i
                if (j >= 0) {
                    right[j] = i;
                } else {
                    right[j + n] = i + n;
                }
            }
            pos[nums[(i + n) % n]] = i;
        }

        for (int& i : queries) {
            int l = left[i];
            i = i - l == n ? -1 : min(i - l, right[i] - i);
        }
        return queries;
    }
};

###go

func solveQueries(nums []int, queries []int) []int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
pos := map[int]int{}
for i := -n; i < n; i++ {
if i >= 0 {
j := pos[nums[i]]
left[i] = j
// 对于左边的 j 来说，它的 right 就是 i
if j >= 0 {
right[j] = i
} else {
right[j+n] = i + n
}
}
pos[nums[(i+n)%n]] = i
}

for qi, i := range queries {
l := left[i]
if i-l == n {
queries[qi] = -1
} else {
queries[qi] = min(i-l, right[i]-i)
}
}
return queries
}

优化（二）

上面的写法并不是真正的一次遍历，因为遍历了 $\textit{nums}$ 两次。

要做到真正的一次遍历，需要记录每个元素首次出现的位置和最后一次出现的位置。

###py

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        left = [0] * n
        right = [0] * n
        first = {}  # 记录首次出现的位置
        last = {}  # 记录最后一次出现的位置
        for i, x in enumerate(nums):
            left[i] = j = last.get(x, -1)
            if j >= 0:
                right[j] = i
            if x not in first:
                first[x] = i
            last[x] = i

        for qi, i in enumerate(queries):
            l = left[i] if left[i] >= 0 else last[nums[i]] - n
            if i - l == n:
                queries[qi] = -1
            else:
                r = right[i] or first[nums[i]] + n
                queries[qi] = min(i - l, r - i)
        return queries

###java

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Map<Integer, Integer> first = new HashMap<>(); // 记录首次出现的位置
        Map<Integer, Integer> last = new HashMap<>(); // 记录最后一次出现的位置
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            left[i] = last.getOrDefault(x, -1);
            if (left[i] >= 0) {
                right[left[i]] = i;
            }
            first.putIfAbsent(x, i);
            last.put(x, i);
        }

        List<Integer> ans = new ArrayList<>(queries.length);
        for (int i : queries) {
            int l = left[i] >= 0 ? left[i] : last.get(nums[i]) - n;
            if (i - l == n) {
                ans.add(-1);
            } else {
                int r = right[i] > 0 ? right[i] : first.get(nums[i]) + n;
                ans.add(Math.min(i - l, r - i));
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        vector<int> left(n), right(n);
        unordered_map<int, int> first, last; // 记录首次出现和最后一次出现的位置
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            left[i] = last.contains(x) ? last[x] : -1;
            if (left[i] >= 0) {
                right[left[i]] = i;
            }
            if (!first.contains(x)) {
                first[x] = i;
            }
            last[x] = i;
        }

        for (int& i : queries) {
            int l = left[i] >= 0 ? left[i] : last[nums[i]] - n;
            if (i - l == n) {
                i = -1;
            } else {
                int r = right[i] ? right[i] : first[nums[i]] + n;
                i = min(i - l, r - i);
            }
        }
        return queries;
    }
};

###go

func solveQueries(nums []int, queries []int) []int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
first := map[int]int{} // 首次出现的位置
last := map[int]int{}  // 最后一次出现的位置
for i, x := range nums {
j, ok := last[nums[i]]
if ok {
left[i] = j
right[j] = i
} else {
left[i] = -1
}
if _, ok := first[x]; !ok {
first[x] = i
}
last[x] = i
}

for qi, i := range queries {
l := left[i]
if l < 0 {
l = last[nums[i]] - n
}
if i-l == n {
queries[qi] = -1
} else {
r := right[i]
if r == 0 {
r = first[nums[i]] + n
}
queries[qi] = min(i-l, r-i)
}
}
return queries
}

复杂度分析

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

相似题目

• 2080. 区间内查询数字的频率 1702

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 【本题相关】二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

一、贪心性质

看上去，一个工厂修理一段连续的机器人是最优的。为什么？

先排序，设工厂的位置为 $f_1 < f_2 < \cdots < f_n$，机器人的位置为 $r_1 < r_2 < \cdots < r_m$。

注：题目保证工厂的位置互不相同，机器人的位置互不相同。

对于序列中的两个工厂 $f_a$ 和 $f_b$（$a<b$），两个机器人 $r_i$ 和 $r_j$（$i<j$），对比如下两个方案：

• $r_i$ 去 $f_a$，$r_j$ 去 $f_b$，移动距离之和为 $|r_i - f_a| + |r_j - f_b|$。
• $r_i$ 去 $f_b$，$r_j$ 去 $f_a$，移动距离之和为 $|r_i - f_b| + |r_j - f_a|$。

下图是其中一种情况。

{:width=600px}

用分类讨论可以证明，$|r_i - f_a| + |r_j - f_b|\le |r_i - f_b| + |r_j - f_a|$。

换句话说，存在这样的最优解，对于任意一对机器人 $i$ 和 $j$（$i<j$），机器人 $i$ 去的工厂编号 $\le $ 机器人 $j$ 去的工厂编号。同一个工厂修理的机器人，在排序后的机器人序列里是连续的一段。

二、寻找子问题

在示例 1 中，我们要解决的问题（原问题）是：

• 工厂下标区间 $[0,1]$ 修理机器人下标区间 $[0,2]$，机器人移动的最小总距离。

从右往左思考，枚举最后一个工厂修多少个机器人：

• 修 $0$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,2]$，机器人移动的最小总距离。
• 修 $1$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,1]$，机器人移动的最小总距离。
• 修 $2$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,0]$，机器人移动的最小总距离。
• 至多修 $2$ 个，因为 $\textit{limit}_1 = 2$。

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

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

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

根据上面的讨论，定义 $\textit{dfs}(i,j)$ 表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j]$，机器人移动的最小总距离。

枚举工厂 $i$ 修 $k=0,1,2\ldots,\min(j+1,\textit{limit}_i)$ 个机器人，问题变成工厂下标区间 $[0,i-1]$ 修理机器人下标区间 $[0,j-k]$，机器人移动的最小总距离，即 $\textit{dfs}(i-1, j-k)$，再加上机器人 $[j-k+1, j]$ 到工厂 $i$ 的距离。

对所有 $k$ 取最小值，就得到了 $\textit{dfs}(i,j)$，即

$$
\textit{dfs}(i,j) = \min_{k=0}^{\min(j+1,\textit{limit}i)} \left{ \textit{dfs}(i-1, j-k) + \sum{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]| \right}
$$

由于 $k$ 每增加 $1$，距离和 $\displaystyle\sum_{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]|$ 就会新增一项 $|\textit{robot}[j-k+1]-\textit{position}[i]|$，所以可以用一个变量 $\textit{disSum}$ 维护距离和，而不是对每个 $k$ 都跑一个循环算距离和。

递归边界：

• $\textit{dfs}(i,-1)=0$。没有机器人了，总移动距离为 $0$。
• $\textit{dfs}(-1,j)=\infty\ (j\ge 0)$。没有工厂，但还有剩下的机器人，不合法。返回 $\infty$，这样上面公式中的 $\min$ 不会取到不合法的情况。

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

注：题目保证所有机器人都可以被维修。

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

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

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

⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。

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

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

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()

        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if j < 0:  # 所有机器人都修完了
                return 0
            if i < 0:  # 还有机器人没修，但没有工厂了
                return inf

            # 工厂 i 不修机器人
            res = dfs(i - 1, j)

            position, limit = factory[i]
            dis_sum = 0
            # 枚举修 k 个机器人
            for k in range(1, min(j + 1, limit) + 1):
                dis_sum += abs(robot[j - k + 1] - position)
                res = min(res, dfs(i - 1, j - k) + dis_sum)

            return res

        return dfs(len(factory) - 1, len(robot) - 1)

class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int n = factory.length;
        int m = robot.length;
        long[][] memo = new long[n][m];
        for (long[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }

        return dfs(n - 1, m - 1, robot, factory, memo);
    }

    private long dfs(int i, int j, int[] robot, int[][] factory, long[][] memo) {
        if (j < 0) { // 所有机器人都修完了
            return 0;
        }
        if (i < 0) { // 还有机器人没修，但没有工厂了
            return Long.MAX_VALUE / 2; // 避免加法溢出
        }

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

        // 工厂 i 不修机器人
        long res = dfs(i - 1, j, robot, factory, memo);

        int position = factory[i][0];
        int limit = factory[i][1];
        long disSum = 0;
        // 枚举修 k 个机器人
        for (int k = 1; k <= Math.min(j + 1, limit); k++) {
            disSum += Math.abs(robot[j - k + 1] - position);
            res = Math.min(res, dfs(i - 1, j - k, robot, factory, memo) + disSum);
        }

        memo[i][j] = res; // 记忆化
        return res;
    }
}

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        ranges::sort(factory, {}, [](auto& f) { return f[0]; });
        ranges::sort(robot);

        int n = factory.size(), m = robot.size();
        vector memo(n, vector<long long>(m, -1)); // -1 表示没有计算过

        auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
            if (j < 0) { // 所有机器人都修完了
                return 0;
            }
            if (i < 0) { // 还有机器人没修，但没有工厂了
                return LLONG_MAX / 2; // 避免加法溢出
            }

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

            // 工厂 i 不修机器人
            res = dfs(i - 1, j);

            int position = factory[i][0], limit = factory[i][1];
            long long dis_sum = 0;
            // 枚举修 k 个机器人
            for (int k = 1; k <= min(j + 1, limit); k++) {
                dis_sum += abs(robot[j - k + 1] - position);
                res = min(res, dfs(i - 1, j - k) + dis_sum);
            }

            return res;
        };

        return dfs(n - 1, m - 1);
    }
};

func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)

n, m := len(factory), len(robot)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}

var dfs func(int, int) int
dfs = func(i, j int) (res int) {
if j < 0 { // 所有机器人都修完了
return 0
}
if i < 0 { // 还有机器人没修，但没有工厂了
return math.MaxInt / 2 // 避免加法溢出
}

p := &memo[i][j]
if *p != -1 { // 之前计算过
return *p
}
defer func() { *p = res }() // 记忆化

// 工厂 i 不修机器人
res = dfs(i-1, j)

position, limit := factory[i][0], factory[i][1]
disSum := 0
// 枚举修 k 个机器人
for k := 1; k <= min(j+1, limit); k++ {
disSum += abs(robot[j-k+1] - position)
res = min(res, dfs(i-1, j-k)+disSum)
}
return
}

return int64(dfs(n-1, m-1))
}

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

复杂度分析

• 时间复杂度：$\mathcal{O}(nm^2 + n\log n)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(nm)$，单个状态的计算时间为 $\mathcal{O}(m)$，所以记忆化搜索的时间复杂度为 $\mathcal{O}(nm^2)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度，由于 $\mathcal{O}(m\log m)$ 比 $\mathcal{O}(nm^2)$ 小，可以省略。
• 空间复杂度：$\mathcal{O}(nm)$。保存多少状态，就需要多少空间。

五、1:1 翻译成递推

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

具体来说，$f[i+1][j+1]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j]$，机器人移动的最小总距离。这里 $+1$ 是为了把 $\textit{dfs}(i,-1)$ 和 $\textit{dfs}(-1,j)$ 也翻译过来，这样我们可以把 $f[i][0]$ 和 $f[0][j]$ 作为初始值。

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

$$
f[i+1][j+1] = \min_{k=0}^{\min(\textit{limit}i, j+1)} \left{ f[i][j-k+1] + \sum{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]| \right}
$$

初始值 $f[i][0] = 0$ 以及 $f[0][j] = \infty\ (j\ge 1)$，翻译自递归边界。

答案为 $f[n][m]$，翻译自递归入口。

写法一

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()

        n, m = len(factory), len(robot)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0][1:] = [inf] * m

        for i, (position, limit) in enumerate(factory):
            for j in range(m):
                # 工厂 i 不修机器人
                res = f[i][j + 1]

                # 枚举修 k 个机器人
                dis_sum = 0
                for k in range(1, min(j + 1, limit) + 1):
                    dis_sum += abs(robot[j - k + 1] - position)
                    res = min(res, f[i][j - k + 1] + dis_sum)

                f[i + 1][j + 1] = res

        return f[n][m]

class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int n = factory.length;
        int m = robot.length;
        long[][] f = new long[n + 1][m + 1];
        Arrays.fill(f[0], Long.MAX_VALUE / 2);
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int position = factory[i][0];
            int limit = factory[i][1];
            for (int j = 0; j < m; j++) {
                // 工厂 i 不修机器人
                long res = f[i][j + 1];

                // 枚举修 k 个机器人
                long disSum = 0;
                for (int k = 1; k <= Math.min(j + 1, limit); k++) {
                    disSum += Math.abs(robot[j - k + 1] - position);
                    res = Math.min(res, f[i][j - k + 1] + disSum);
                }

                f[i + 1][j + 1] = res;
            }
        }

        return f[n][m];
    }
}

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        ranges::sort(factory, {}, [](auto& f) { return f[0]; });
        ranges::sort(robot);

        int n = factory.size(), m = robot.size();
        vector f(n + 1, vector<long long>(m + 1));
        fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);

        for (int i = 0; i < n; i++) {
            int position = factory[i][0], limit = factory[i][1];
            for (int j = 0; j < m; j++) {
                // 工厂 i 不修机器人
                long long res = f[i][j + 1];

                // 枚举修 k 个机器人
                long long dis_sum = 0;
                for (int k = 1; k <= min(j + 1, limit); k++) {
                    dis_sum += abs(robot[j - k + 1] - position);
                    res = min(res, f[i][j - k + 1] + dis_sum);
                }

                f[i + 1][j + 1] = res;
            }
        }

        return f[n][m];
    }
};

func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)

n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}

for i, fac := range factory {
position, limit := fac[0], fac[1]
for j := range m {
// 工厂 i 不修机器人
res := f[i][j+1]

// 枚举修 k 个机器人
disSum := 0
for k := 1; k <= min(j+1, limit); k++ {
disSum += abs(robot[j-k+1] - position)
res = min(res, f[i][j-k+1]+disSum)
}

f[i+1][j+1] = res
}
}

return int64(f[n][m])
}

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

写法二

为了方便大家阅读下一章（单调队列优化），先微调一下状态定义和状态转移方程。

把 $j+1$ 替换成 $j$，定义 $f[i+1][j]$ 表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j-1]$，机器人移动的最小总距离。

状态转移方程为：

$$
f[i+1][j] = \min_{k=0}^{\min(\textit{limit}i, j)} \left{ f[i][j-k] + \sum{p=j-k}^{j-1} |\textit{robot}[p]-\textit{position}[i]| \right}
$$

这样可以少写很多 $+1$。

在 $k$ 从 $0$ 增大到 $\min(\textit{limit}_i, j)$ 的过程中，$j-k$ 从 $j$ 减小到 $\max(j-\textit{limit}_i, 0)$。

把 $j-k$ 替换成 $k$，状态转移方程为：

$$
f[i+1][j] = \min_{k=\max(j-\textit{limit}i, 0)}^{j} \left{ f[i][k] + \sum{p=k}^{j-1} |\textit{robot}[p]-\textit{position}[i]| \right}
$$

这样转移方程就更干净了，从而方便我们进一步优化。

注：这相当于在枚举工厂 $i$ 修理的最左边的机器人的编号 $k$。

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()

        n, m = len(factory), len(robot)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0][1:] = [inf] * m

        for i, (position, limit) in enumerate(factory):
            for j in range(1, m + 1):
                # 工厂 i 不修机器人
                res = f[i][j]

                # 修理下标在 [k, j-1] 中的机器人
                dis_sum = 0
                for k in range(j - 1, max(j - limit, 0) - 1, -1):
                    dis_sum += abs(robot[k] - position)
                    res = min(res, f[i][k] + dis_sum)

                f[i + 1][j] = res

        return f[n][m]

class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int n = factory.length;
        int m = robot.length;
        long[][] f = new long[n + 1][m + 1];
        Arrays.fill(f[0], Long.MAX_VALUE / 2);
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int position = factory[i][0];
            int limit = factory[i][1];
            for (int j = 1; j <= m; j++) {
                // 工厂 i 不修机器人
                long res = f[i][j];

                // 修理下标在 [k, j-1] 中的机器人
                long disSum = 0;
                for (int k = j - 1; k >= Math.max(j - limit, 0); k--) {
                    disSum += Math.abs(robot[k] - position);
                    res = Math.min(res, f[i][k] + disSum);
                }

                f[i + 1][j] = res;
            }
        }

        return f[n][m];
    }
}

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        ranges::sort(factory, {}, [](auto& f) { return f[0]; });
        ranges::sort(robot);

        int n = factory.size(), m = robot.size();
        vector f(n + 1, vector<long long>(m + 1));
        fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);

        for (int i = 0; i < n; i++) {
            int position = factory[i][0], limit = factory[i][1];
            for (int j = 1; j <= m; j++) {
                // 工厂 i 不修机器人
                long long res = f[i][j];

                // 修理下标在 [k, j-1] 中的机器人
                long long dis_sum = 0;
                for (int k = j - 1; k >= max(j - limit, 0); k--) {
                    dis_sum += abs(robot[k] - position);
                    res = min(res, f[i][k] + dis_sum);
                }

                f[i + 1][j] = res;
            }
        }

        return f[n][m];
    }
};

func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)

n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}

for i, fac := range factory {
position, limit := fac[0], fac[1]
for j := 1; j <= m; j++ {
// 工厂 i 不修机器人
res := f[i][j]

// 修理下标在 [k, j-1] 中的机器人
disSum := 0
for k := j - 1; k >= max(j-limit, 0); k-- {
disSum += abs(robot[k] - position)
res = min(res, f[i][k]+disSum)
}

f[i+1][j] = res
}
}

return int64(f[n][m])
}

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

复杂度分析

• 时间复杂度：$\mathcal{O}(nm^2 + n\log n)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。DP 的时间复杂度为 $\mathcal{O}(nm^2)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度，由于 $\mathcal{O}(m\log m)$ 比 $\mathcal{O}(nm^2)$ 小，可以省略。
• 空间复杂度：$\mathcal{O}(nm)$。

六、单调队列优化

前置题目：239. 滑动窗口最大值，视频讲解 单调队列【基础算法精讲 27】。

定义 $d_i[p] = |\textit{robot}[p]-\textit{position}[i]|$。

设 $d_i$ 数组的前缀和数组为 $s_i$。关于 $s_i$ 的定义，请看 前缀和。

状态转移方程为：

$$
\begin{aligned}
f[i+1][j] &= \min_{k=\max(j-\textit{limit}i, 0)}^{j} \left{ f[i][k] + s_i[j] - s_i[k]\right} \
&= s_i[j] + \min{k=\max(j-\textit{limit}_i, 0)}^{j} \left{ f[i][k] - s_i[k]\right} \
\end{aligned}
$$

当 $j$ 增大时，$k$ 的范围是一个向右移动的滑动窗口，我们计算的是 $f[i][k] - s_i[k]$ 的滑动窗口最小值。上式的 $\min$ 可以用单调队列优化至均摊 $\mathcal{O}(1)$ 时间复杂度。

答疑

问：对于单调队列优化 DP，什么时候先把元素入队再计算 DP，什么时候先计算 DP 再把元素入队？

答：这取决于计算的 DP 是否包含要入队的元素。如果包含，那就先入队再计算 DP；如果不包含，那就先计算 DP 再入队。本题是前者。

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()

        n, m = len(factory), len(robot)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0][1:] = [inf] * m

        for i, (position, limit) in enumerate(factory):
            dis_sum = list(accumulate((abs(r - position) for r in robot), initial=0))  # 前缀和
            q = deque([(0, 0)])
            for j in range(1, m + 1):
                # 1. 入
                v = f[i][j] - dis_sum[j]
                while q and q[-1][1] >= v:
                    q.pop()
                q.append((j, v))

                # 2. 出
                while q[0][0] < j - limit:
                    q.popleft()

                # 3. 队首为滑动窗口最小值
                f[i + 1][j] = dis_sum[j] + q[0][1]

        return f[n][m]

class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int n = factory.length;
        int m = robot.length;
        long[][] f = new long[n + 1][m + 1];
        Arrays.fill(f[0], Long.MAX_VALUE / 2);
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int position = factory[i][0];
            int limit = factory[i][1];

            long[] disSum = new long[m + 1]; // 前缀和
            for (int j = 0; j < m; j++) {
                disSum[j + 1] = disSum[j] + Math.abs(robot[j] - position);
            }

            Deque<long[]> q = new ArrayDeque<>();
            q.offerLast(new long[]{0, 0});

            for (int j = 1; j <= m; j++) {
                // 1. 入
                long v = f[i][j] - disSum[j];
                while (!q.isEmpty() && q.peekLast()[1] >= v) {
                    q.pollLast();
                }
                q.offerLast(new long[]{j, v});

                // 2. 出
                while (q.peekFirst()[0] < j - limit) {
                    q.pollFirst();
                }

                // 3. 队首为滑动窗口最小值
                f[i + 1][j] = disSum[j] + q.peekFirst()[1];
            }
        }

        return f[n][m];
    }
}

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        ranges::sort(factory, {}, [](auto& f) { return f[0]; });
        ranges::sort(robot);

        int n = factory.size(), m = robot.size();
        vector f(n + 1, vector<long long>(m + 1));
        fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);

        for (int i = 0; i < n; i++) {
            int position = factory[i][0], limit = factory[i][1];

            vector<long long> dis_sum(m + 1); // 前缀和
            for (int j = 0; j < m; j++) {
                dis_sum[j + 1] = dis_sum[j] + abs(robot[j] - position);
            }

            deque<pair<int, long long>> q;
            q.emplace_back(0, 0);

            for (int j = 1; j <= m; j++) {
                // 1. 入
                long long v = f[i][j] - dis_sum[j];
                while (!q.empty() && q.back().second >= v) {
                    q.pop_back();
                }
                q.emplace_back(j, v);

                // 2. 出
                while (q.front().first < j - limit) {
                    q.pop_front();
                }

                // 3. 队首为滑动窗口最小值
                f[i + 1][j] = dis_sum[j] + q.front().second;
            }
        }

        return f[n][m];
    }
};

func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)

n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}

for i, fac := range factory {
position, limit := fac[0], fac[1]

disSum := make([]int, m+1) // 前缀和
for j, r := range robot {
disSum[j+1] = disSum[j] + abs(r-position)
}

type pair struct{ i, v int }
q := []pair{{0, 0}}

for j := 1; j <= m; j++ {
// 1. 入
v := f[i][j] - disSum[j]
for len(q) > 0 && q[len(q)-1].v >= v {
q = q[:len(q)-1]
}
q = append(q, pair{j, v})

// 2. 出
for q[0].i < j-limit {
q = q[1:]
}

// 3. 队首为滑动窗口最小值
f[i+1][j] = disSum[j] + q[0].v
}
}

return int64(f[n][m])
}

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

复杂度分析

• 时间复杂度：$\mathcal{O}(nm + n\log n + m\log m)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。对于三重循环里面的二重循环，站在每个元素的视角看，这个元素在二重循环中最多入队出队各一次，因此二重循环的循环次数之和是 $\mathcal{O}(m)$，所以三重循环的时间复杂度是 $\mathcal{O}(nm)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度。
• 空间复杂度：$\mathcal{O}(nm)$。

七、空间优化

观察上面的代码，计算 $f[i+1][j]$ 只会用到 $f[i][j]$。

所以只需要一个长为 $m+1$ 的一维数组 $f$，我们直接把计算结果覆盖到 $f[j]$ 中。

此外，前缀和可以一边枚举 $j$ 一边计算，从而优化成一个变量。

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()

        m = len(robot)
        f = [0] + [inf] * m

        for position, limit in factory:
            dis_sum = 0
            q = deque([(0, 0)])
            for j, r in enumerate(robot, 1):  # r = robot[j - 1]
                dis_sum += abs(r - position)

                # 1. 入
                v = f[j] - dis_sum
                while q and q[-1][1] >= v:
                    q.pop()
                q.append((j, v))

                # 2. 出
                while q[0][0] < j - limit:
                    q.popleft()

                # 3. 队首为滑动窗口最小值
                f[j] = dis_sum + q[0][1]

        return f[m]

// 更快的写法见【Java 写法二】
class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int m = robot.length;
        long[] f = new long[m + 1];
        Arrays.fill(f, Long.MAX_VALUE / 2);
        f[0] = 0;

        for (int[] fac : factory) {
            int position = fac[0];
            int limit = fac[1];

            long disSum = 0;
            Deque<long[]> q = new ArrayDeque<>(); // ArrayDeque 慢，更快的写法见【Java 写法二】
            q.offerLast(new long[]{0, 0});

            for (int j = 1; j <= m; j++) {
                disSum += Math.abs(robot[j - 1] - position);

                // 1. 入
                long v = f[j] - disSum;
                while (!q.isEmpty() && q.peekLast()[1] >= v) {
                    q.pollLast();
                }
                q.offerLast(new long[]{j, v});

                // 2. 出
                while (q.peekFirst()[0] < j - limit) {
                    q.pollFirst();
                }

                // 3. 队首为滑动窗口最小值
                f[j] = disSum + q.peekFirst()[1];
            }
        }

        return f[m];
    }
}

class Solution {
    public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
        int[] robot = robotList.stream().mapToInt(i -> i).toArray();
        Arrays.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        int m = robot.length;
        long[] f = new long[m + 1];
        Arrays.fill(f, Long.MAX_VALUE / 2);
        f[0] = 0;

        int[] idxQ = new int[m + 1]; // 用两个数组模拟 ArrayDeque
        long[] valQ = new long[m + 1];

        for (int[] fac : factory) {
            int position = fac[0];
            int limit = fac[1];

            long disSum = 0;
            int head = 0;
            int tail = 0;
            idxQ[tail] = 0;
            valQ[tail] = 0;

            for (int j = 1; j <= m; j++) {
                disSum += Math.abs(robot[j - 1] - position);

                // 1. 入
                long v = f[j] - disSum;
                while (head <= tail && valQ[tail] >= v) {
                    tail--;
                }
                tail++;
                idxQ[tail] = j;
                valQ[tail] = v;

                // 2. 出
                while (idxQ[head] < j - limit) {
                    head++;
                }

                // 3. 队首为滑动窗口最小值
                f[j] = disSum + valQ[head];
            }
        }

        return f[m];
    }
}

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        ranges::sort(factory, {}, [](auto& f) { return f[0]; });
        ranges::sort(robot);

        int m = robot.size();
        vector<long long> f(m + 1, LLONG_MAX / 2);
        f[0] = 0;

        for (auto& fac : factory) {
            int position = fac[0], limit = fac[1];

            long long dis_sum = 0;
            deque<pair<int, long long>> q;
            q.emplace_back(0, 0);

            for (int j = 1; j <= m; j++) {
                int r = robot[j - 1];
                dis_sum += abs(r - position);

                // 1. 入
                long long v = f[j] - dis_sum;
                while (!q.empty() && q.back().second >= v) {
                    q.pop_back();
                }
                q.emplace_back(j, v);

                // 2. 出
                while (q.front().first < j - limit) {
                    q.pop_front();
                }

                // 3. 队首为滑动窗口最小值
                f[j] = dis_sum + q.front().second;
            }
        }

        return f[m];
    }
};

func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)

m := len(robot)
f := make([]int, m+1)
for j := 1; j <= m; j++ {
f[j] = math.MaxInt / 2
}

for _, fac := range factory {
position, limit := fac[0], fac[1]

disSum := 0
type pair struct{ i, v int }
q := []pair{{0, 0}}

for j, r := range robot {
j++
disSum += abs(r - position)

// 1. 入
v := f[j] - disSum
for len(q) > 0 && q[len(q)-1].v >= v {
q = q[:len(q)-1]
}
q = append(q, pair{j, v})

// 2. 出
for q[0].i < j-limit {
q = q[1:]
}

// 3. 队首为滑动窗口最小值
f[j] = disSum + q[0].v
}
}

return int64(f[m])
}

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

复杂度分析

• 时间复杂度：$\mathcal{O}(nm + n\log n + m\log m)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。对于三重循环里面的二重循环，站在每个元素的视角看，这个元素在二重循环中最多入队出队各一次，因此二重循环的循环次数之和是 $\mathcal{O}(m)$，所以三重循环的时间复杂度是 $\mathcal{O}(nm)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度。
• 空间复杂度：$\mathcal{O}(m)$。忽略排序的栈开销。

专题训练

见下面动态规划题单的「五、划分型 DP」和「§11.3 单调队列优化 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

方法一：从左到右遍历

如果 $\textit{nums}[i] = \textit{target}$，用 $|i-\textit{start}|$ 更新答案的最小值。

题目保证 $\textit{target}$ 在 $\textit{nums}$ 中。

###py

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        ans = inf
        for i, x in enumerate(nums):
            if x == target:
                ans = min(ans, abs(i - start))
        return ans

###py

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        return min(abs(i - start) for i, x in enumerate(nums) if x == target)

###java

class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                ans = Math.min(ans, Math.abs(i - start));
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int getMinDistance(vector<int>& nums, int target, int start) {
        int ans = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                ans = min(ans, abs(i - start));
            }
        }
        return ans;
    }
};

###c

int getMinDistance(int* nums, int numsSize, int target, int start) {
    int ans = numsSize;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            ans = MIN(ans, abs(i - start));
        }
    }
    return ans;
}

###go

func getMinDistance(nums []int, target int, start int) int {
ans := math.MaxInt
for i, x := range nums {
if x == target {
ans = min(ans, abs(i-start))
}
}
return ans
}

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

###js

var getMinDistance = function(nums, target, start) {
    let ans = nums.length;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            ans = Math.min(ans, Math.abs(i - start));
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn get_min_distance(nums: Vec<i32>, target: i32, start: i32) -> i32 {
        let mut ans = i32::MAX;
        for (i, x) in nums.into_iter().enumerate() {
            if x == target {
                ans = ans.min((i as i32 - start).abs());
            }
        }
        ans
    }
}

复杂度分析

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

方法二：从 start 往两侧遍历

枚举答案 $k=0,1,2,\ldots$，判断 $\textit{nums}[\textit{start}-k] = \textit{target}$ 或者 $\textit{nums}[\textit{start}+k] = \textit{target}$ 是否成立，如果成立，直接返回 $k$。

题目保证 $\textit{target}$ 在 $\textit{nums}$ 中。

###py

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        for k in count(0):  # 枚举 k=0,1,2,...
            if start >= k and nums[start - k] == target or \
               start + k < len(nums) and nums[start + k] == target:
                return k

###java

class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        for (int k = 0; ; k++) {
            if (start >= k && nums[start - k] == target ||
                start + k < nums.length && nums[start + k] == target) {
                return k;
            }
        }
    }
}

###cpp

class Solution {
public:
    int getMinDistance(vector<int>& nums, int target, int start) {
        for (int k = 0; ; k++) {
            if (start >= k && nums[start - k] == target ||
                start + k < nums.size() && nums[start + k] == target) {
                return k;
            }
        }
    }
};

###c

int getMinDistance(int* nums, int numsSize, int target, int start) {
    for (int k = 0; ; k++) {
        if (start >= k && nums[start - k] == target ||
            start + k < numsSize && nums[start + k] == target) {
            return k;
        }
    }
}

###go

func getMinDistance(nums []int, target int, start int) int {
for k := 0; ; k++ {
if start >= k && nums[start-k] == target ||
start+k < len(nums) && nums[start+k] == target {
return k
}
}
}

###js

var getMinDistance = function(nums, target, start) {
    for (let k = 0; ; k++) {
        if (start >= k && nums[start - k] === target ||
            start + k < nums.length && nums[start + k] === target) {
            return k;
        }
    }
};

###rust

impl Solution {
    pub fn get_min_distance(nums: Vec<i32>, target: i32, start: i32) -> i32 {
        let start = start as usize;
        let mut k = 0;
        loop {
            if start >= k && nums[start - k] == target ||
               start + k < nums.len() && nums[start + k] == target {
                return k as _;
            }
            k += 1;
        }
    }
}

复杂度分析

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

思考题

改成输入一个 $\textit{queries}$ 数组，每个 $\textit{queries}[i] = [\textit{target}_i, \textit{start}_i]$。

如何快速回答每个询问？

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

相似题目：3488. 距离最小相等元素查询

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

一、分析

示例 1 的 $\textit{word} = \texttt{CAKE}$，敲完 $\texttt{E}$ 就结束了，所以最后一定有一根手指停在 $\texttt{E}$。

另一根手指呢？最后一定停在 $\texttt{K}$ 吗？不一定，如果第一根手指输入 $\texttt{CA}$，第二根手指输入 $\texttt{KE}$，那么第一根手指最后会停在 $\texttt{A}$，第二根手指最后会停在 $\texttt{E}$。

只要我们能实时跟踪两根手指的位置（在哪个字母），就能暴力搜索所有输入的过程。

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

根据上面的讨论，定义 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$ 表示在手指 1 位于字母 $\textit{finger}_1$，手指 2 位于字母 $\textit{finger}_2$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。

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

讨论用哪根手指输入 $\textit{word}[i]$：

• 用手指 1，那么接下来要解决的问题是，在手指 1 位于字母 $\textit{word}[i]$，手指 2 位于字母 $\textit{finger}_2$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i-1]$ 的最小移动总距离，即 $\textit{dfs}(i-1, \textit{word}[i],\textit{finger}_2)$，加上从 $\textit{finger}_1$ 到 $\textit{word}[i]$ 的距离。
• 用手指 2，那么接下来要解决的问题是，在手指 1 位于字母 $\textit{finger}_1$，手指 2 位于字母 $\textit{word}[i]$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i-1]$ 的最小移动总距离，即 $\textit{dfs}(i-1, \textit{finger}_1,\textit{word}[i])$，加上从 $\textit{finger}_2$ 到 $\textit{word}[i]$ 的距离。

这两种情况取最小值，就得到了 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$，即

$$
\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2) = \min
\begin{cases}
\textit{dfs}(i-1, \textit{word}[i],\textit{finger}_2) + \textit{dis}[\textit{finger}_1][\textit{word}[i]] \
\textit{dfs}(i-1, \textit{finger}_1,\textit{word}[i]) + \textit{dis}[\textit{finger}_2][\textit{word}[i]] \
\end{cases}
$$

其中 $\textit{dis}[x][y]$ 表示从字母 $x$ 到字母 $y$ 的距离。这个二维数组可以在跑 $\textit{dfs}$ 之前预处理出来。

递归边界：$\textit{dfs}(-1, \textit{finger}_1, \textit{finger}_2)=0$。没有字母需要输入，无需移动。

递归入口：$\textit{dfs}(n-2, \textit{word}[n-1], \textit{finger}_2)$。最后一定有一根手指在 $\textit{word}[n-1]$，另一根手指的位置不确定，枚举 $\textit{finger}_2$。

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

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

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

⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。

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

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

###py

# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]

class Solution:
    def minimumDistance(self, word: str) -> int:
        word = [ord(ch) - ord('A') for ch in word]  # 避免在 dfs 中频繁调用 ord

        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, finger1: int, finger2: int) -> int:
            if i < 0:
                return 0

            # 手指 1 移到 word[i]
            res1 = dfs(i - 1, word[i], finger2) + dis[finger1][word[i]]

            # 手指 2 移到 word[i]
            res2 = dfs(i - 1, finger1, word[i]) + dis[finger2][word[i]]

            return min(res1, res2)

        n = len(word)
        # 最后一定有一根手指在 word[-1]，另一根手指的位置不确定，枚举
        return min(dfs(n - 2, word[-1], finger2) for finger2 in range(26))

###java

class Solution {
    private static final int[][] dis = new int[26][26];

    static {
        // 预处理两个字母的距离
        final int COLUMN = 6;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
            }
        }
    }

    public int minimumDistance(String word) {
        char[] s = word.toCharArray();
        int n = s.length;

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

        int ans = Integer.MAX_VALUE;
        // 最后一定有一根手指在 s[n-1]，另一根手指的位置不确定，枚举
        for (int finger2 = 0; finger2 < 26; finger2++) {
            ans = Math.min(ans, dfs(n - 2, s[n - 1] - 'A', finger2, s, memo));
        }
        return ans;
    }

    private int dfs(int i, int finger1, int finger2, char[] word, int[][][] memo) {
        if (i < 0) {
            return 0;
        }

        if (memo[i][finger1][finger2] != -1) { // 之前计算过
            return memo[i][finger1][finger2];
        }

        // 手指 1 移到 word[i]
        int w = word[i] - 'A';
        int res1 = dfs(i - 1, w, finger2, word, memo) + dis[finger1][w];

        // 手指 2 移到 word[i]
        int res2 = dfs(i - 1, finger1, w, word, memo) + dis[finger2][w];

        int res = Math.min(res1, res2);
        memo[i][finger1][finger2] = res; // 记忆化
        return res;
    }
}

###cpp

int dis[26][26];

auto init = [] {
    // 预处理两个字母的距离
    constexpr int COLUMN = 6;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
        }
    }
    return 0;
}();

class Solution {
public:
    int minimumDistance(string word) {
        int n = word.size();
        vector memo(n, vector(26, vector<int>(26, -1))); // -1 表示没有计算过

        auto dfs = [&](this auto&& dfs, int i, int finger1, int finger2) -> int {
            if (i < 0) {
                return 0;
            }

            int& res = memo[i][finger1][finger2]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }

            // 手指 1 移到 word[i]
            int w = word[i] - 'A';
            int res1 = dfs(i - 1, w, finger2) + dis[finger1][w];

            // 手指 2 移到 word[i]
            int res2 = dfs(i - 1, finger1, w) + dis[finger2][w];

            res = min(res1, res2);
            return res;
        };

        int ans = INT_MAX;
        // 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
        for (int finger2 = 0; finger2 < 26; finger2++) {
            ans = min(ans, dfs(n - 2, word[n - 1] - 'A', finger2));
        }
        return ans;
    }
};

###go

var dis [26][26]int

func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}

func minimumDistance(word string) int {
n := len(word)
memo := make([][26][26]int, n)

var dfs func(int, byte, byte) int
dfs = func(i int, finger1, finger2 byte) (res int) {
if i < 0 {
return 0
}

p := &memo[i][finger1][finger2]
if *p != 0 { // 之前计算过
return *p - 1
}
defer func() { *p = res + 1 }() // 记忆化的时候加一，这样就无需初始化 memo 为 -1 了

// 手指 1 移到 word[i]
w := word[i] - 'A'
res1 := dfs(i-1, w, finger2) + dis[finger1][w]

// 手指 2 移到 word[i]
res2 := dfs(i-1, finger1, w) + dis[finger2][w]

return min(res1, res2)
}

ans := math.MaxInt
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for finger2 := range byte(26) {
ans = min(ans, dfs(n-2, word[n-1]-'A', finger2))
}
return ans
}

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

复杂度分析

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

• 时间复杂度：$\mathcal{O}(n|\Sigma|)$ 或 $\mathcal{O}(n|\Sigma|^2)$，其中 $n$ 是 $\textit{word}$ 的长度，$|\Sigma|=26$ 是字符集合的大小。如果用哈希表保存状态，则时间复杂度为 $\mathcal{O}(n|\Sigma|)$，否则瓶颈在创建 $\textit{memo}$ 数组上。理由见下一章。
• 空间复杂度：$\mathcal{O}(n|\Sigma|)$ 或 $\mathcal{O}(n|\Sigma|^2)$。理由见下一章。

四、状态优化

回顾上面的代码，在输入 $\textit{word}[i]$ 之前，一定有一根手指在 $\textit{word}[i+1]$。这意味着，知道了 $i$，就知道了其中一根手指的位置。所以 $\textit{finger}_1$ 和 $\textit{finger}_2$ 中的一个是多余的。

定义 $\textit{dfs}(i, \textit{anotherFinger})$ 表示在一根手指位于字母 $\textit{word}[i+1]$，另一根手指位于字母 $\textit{anotherFinger}$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。

讨论用哪根手指输入 $\textit{word}[i]$：

• 用位于 $\textit{word}[i+1]$ 的手指输入 $\textit{word}[i]$，那么另一根手指仍然位于字母 $\textit{anotherFinger}$，所以接下来要解决的问题是，在一根手指位于字母 $\textit{word}[i]$，另一根手指位于字母 $\textit{anotherFinger}$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i-1]$ 的最小移动总距离，即 $\textit{dfs}(i-1, \textit{anotherFinger})$，加上从 $\textit{word}[i+1]$ 到 $\textit{word}[i]$ 的距离。
• 用位于 $\textit{anotherFinger}$ 的手指输入 $\textit{word}[i]$，那么位于 $\textit{word}[i+1]$ 的手指就变成了「另一根手指」，所以接下来要解决的问题是，在一根手指位于字母 $\textit{word}[i]$，另一根手指位于字母 $\textit{word}[i+1]$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i-1]$ 的最小移动总距离，即 $\textit{dfs}(i-1, \textit{word}[i+1])$，加上从 $\textit{anotherFinger}$ 到 $\textit{word}[i]$ 的距离。

这两种情况取最小值，就得到了 $\textit{dfs}(i, \textit{anotherFinger})$，即

$$
\textit{dfs}(i, \textit{anotherFinger}) = \min
\begin{cases}
\textit{dfs}(i-1, \textit{anotherFinger}) + \textit{dis}[\textit{word}[i+1]][\textit{word}[i]] \
\textit{dfs}(i-1, \textit{word}[i+1]) + \textit{dis}[\textit{anotherFinger}][\textit{word}[i]] \
\end{cases}
$$

递归边界：$\textit{dfs}(-1, \textit{anotherFinger})=0$。没有字母需要输入，无需移动。

递归入口：$\textit{dfs}(n-2, \textit{anotherFinger})$。最后一定有一根手指在 $\textit{word}[n-1]$，另一根手指的位置不确定，枚举 $\textit{anotherFinger}$。

###py

# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]

class Solution:
    def minimumDistance(self, word: str) -> int:
        word = [ord(ch) - ord('A') for ch in word]  # 避免在 dfs 中频繁调用 ord

        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, another_finger: int) -> int:
            if i < 0:
                return 0

            # 在 word[i+1] 的手指移到 word[i]
            res1 = dfs(i - 1, another_finger) + dis[word[i + 1]][word[i]]

            # 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 another_finger
            res2 = dfs(i - 1, word[i + 1]) + dis[another_finger][word[i]]

            return min(res1, res2)

        n = len(word)
        # 最后一定有一根手指在 word[-1]，另一根手指的位置不确定，枚举
        return min(dfs(n - 2, another_finger) for another_finger in range(26))

###java

class Solution {
    private static final int[][] dis = new int[26][26];

    static {
        // 预处理两个字母的距离
        final int COLUMN = 6;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
            }
        }
    }

    public int minimumDistance(String word) {
        char[] s = word.toCharArray();
        int n = s.length;

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

        int ans = Integer.MAX_VALUE;
        // 最后一定有一根手指在 s[n-1]，另一根手指的位置不确定，枚举
        for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
            ans = Math.min(ans, dfs(n - 2, anotherFinger, s, memo));
        }
        return ans;
    }

    private int dfs(int i, int anotherFinger, char[] word, int[][] memo) {
        if (i < 0) {
            return 0;
        }

        if (memo[i][anotherFinger] != -1) { // 之前计算过
            return memo[i][anotherFinger];
        }

        // 在 word[i+1] 的手指移到 word[i]
        int w = word[i] - 'A';
        int res1 = dfs(i - 1, anotherFinger, word, memo) + dis[word[i + 1] - 'A'][w];

        // 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 anotherFinger
        int res2 = dfs(i - 1, word[i + 1] - 'A', word, memo) + dis[anotherFinger][w];

        int res = Math.min(res1, res2);
        memo[i][anotherFinger] = res; // 记忆化
        return res;
    }
}

###cpp

int dis[26][26];

auto init = [] {
    // 预处理两个字母的距离
    constexpr int COLUMN = 6;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
        }
    }
    return 0;
}();

class Solution {
public:
    int minimumDistance(string word) {
        int n = word.size();
        vector memo(n, vector<int>(26, -1)); // -1 表示没有计算过

        auto dfs = [&](this auto&& dfs, int i, int another_finger) -> int {
            if (i < 0) {
                return 0;
            }

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

            // 在 word[i+1] 的手指移到 word[i]
            int w = word[i] - 'A';
            int res1 = dfs(i - 1, another_finger) + dis[word[i + 1] - 'A'][w];

            // 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 another_finger
            int res2 = dfs(i - 1, word[i + 1] - 'A') + dis[another_finger][w];

            res = min(res1, res2);
            return res;
        };

        int ans = INT_MAX;
        // 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
        for (int another_finger = 0; another_finger < 26; another_finger++) {
            ans = min(ans, dfs(n - 2, another_finger));
        }
        return ans;
    }
};

###go

var dis [26][26]int

func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}

func minimumDistance(word string) int {
n := len(word)
memo := make([][26]int, n)

var dfs func(int, byte) int
dfs = func(i int, anotherFinger byte) (res int) {
if i < 0 {
return 0
}

p := &memo[i][anotherFinger]
if *p != 0 { // 之前计算过
return *p - 1
}
defer func() { *p = res + 1 }() // 记忆化的时候加一，这样就无需初始化 memo 为 -1 了

// 手指 1 移到 word[i]
w := word[i] - 'A'
res1 := dfs(i-1, anotherFinger) + dis[word[i+1]-'A'][w]

// 手指 2 移到 word[i]
res2 := dfs(i-1, word[i+1]-'A') + dis[anotherFinger][w]

return min(res1, res2)
}

ans := math.MaxInt
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for anotherFinger := range byte(26) {
ans = min(ans, dfs(n-2, anotherFinger))
}
return ans
}

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

复杂度分析

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

• 时间复杂度：$\mathcal{O}(n|\Sigma|)$，其中 $n$ 是 $\textit{word}$ 的长度，$|\Sigma|=26$ 是字符集合的大小。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n|\Sigma|)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(n|\Sigma|)$。
• 空间复杂度：$\mathcal{O}(n|\Sigma|)$。保存多少状态，就需要多少空间。

五、1:1 翻译成递推

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

具体来说，$f[i+1][\textit{anotherFinger}]$ 的定义和 $\textit{dfs}(i,\textit{anotherFinger})$ 的定义是一样的，都表示在一根手指位于字母 $\textit{word}[i+1]$，另一根手指位于字母 $\textit{anotherFinger}$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。这里 $+1$ 是为了把 $\textit{dfs}(-1,\textit{anotherFinger})$ 这个状态也翻译过来，这样我们可以把 $f[0]$ 作为初始值。

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

$$
f[i+1][\textit{anotherFinger}] = \min
\begin{cases}
f[i][\textit{anotherFinger}] + \textit{dis}[\textit{word}[i+1]][\textit{word}[i]] \
f[i][\textit{word}[i+1]] + \textit{dis}[\textit{anotherFinger}][\textit{word}[i]] \
\end{cases}
$$

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

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

###py

# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]

class Solution:
    def minimumDistance(self, word: str) -> int:
        f = [[0] * 26 for _ in word]
        for i, (x, y) in enumerate(pairwise(word)):
            x = ord(x) - ord('A')
            y = ord(y) - ord('A')
            for another_finger in range(26):
                f[i + 1][another_finger] = min(f[i][another_finger] + dis[y][x], f[i][y] + dis[another_finger][x])
        return min(f[-1])

###java

class Solution {
    private static final int[][] dis = new int[26][26];

    static {
        // 预处理两个字母的距离
        final int COLUMN = 6;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
            }
        }
    }

    public int minimumDistance(String word) {
        char[] s = word.toCharArray();
        int n = s.length;

        int[][] f = new int[n][26];
        for (int i = 0; i < n - 1; i++) {
            int x = s[i] - 'A';
            int y = s[i + 1] - 'A';
            for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
                f[i + 1][anotherFinger] = Math.min(f[i][anotherFinger] + dis[y][x], f[i][y] + dis[anotherFinger][x]);
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int res : f[n - 1]) {
            ans = Math.min(ans, res);
        }
        return ans;
    }
}

###cpp

int dis[26][26];

auto init = [] {
    // 预处理两个字母的距离
    constexpr int COLUMN = 6;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
        }
    }
    return 0;
}();

class Solution {
public:
    int minimumDistance(string word) {
        int n = word.size();
        vector<array<int, 26>> f(n);
        for (int i = 0; i < n - 1; i++) {
            int x = word[i] - 'A', y = word[i + 1] - 'A';
            for (int another_finger = 0; another_finger < 26; another_finger++) {
                f[i + 1][another_finger] = min(f[i][another_finger] + dis[y][x], f[i][y] + dis[another_finger][x]);
            }
        }
        return ranges::min(f[n - 1]);
    }
};

###go

var dis [26][26]int

func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}

func minimumDistance(word string) int {
n := len(word)
f := make([][26]int, n)

for i := range n - 1 {
x, y := word[i]-'A', word[i+1]-'A'
for anotherFinger := range 26 {
f[i+1][anotherFinger] = min(f[i][anotherFinger]+dis[y][x], f[i][y]+dis[anotherFinger][x])
}
}

return slices.Min(f[n-1][:])
}

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

复杂度分析

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

• 时间复杂度：$\mathcal{O}(n|\Sigma|)$，其中 $n$ 是 $\textit{word}$ 的长度，$|\Sigma|=26$ 是字符集合的大小。
• 空间复杂度：$\mathcal{O}(n|\Sigma|)$。

六、空间优化

由于 $f[i+1]$ 只依赖 $f[i]$，那么 $f[i-1]$ 及其之前的数据就没用了。

例如计算 $f[2]$ 的时候，数组 $f[0]$ 不再使用了。

那么干脆把 $f[2]$ 填到 $f[0]$ 中，$f[3]$ 填到 $f[1]$ 中，$f[4]$ 填到 $f[0]$ 中，$f[5]$ 填到 $f[1]$ 中 …… 只用两个长为 $26$ 的数组滚动计算。

此外，由于 $\textit{dis}[x][y] = \textit{dis}[y][x]$，我们可以交换转移方程中的 $\textit{dis}$ 的两个维度，这样在同一个内层循环中只会访问 $\textit{dis}[x]$ 这一个数组。

###py

COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]

class Solution:
    def minimumDistance(self, word: str) -> int:
        f = [0] * 26
        nf = [0] * 26
        for x, y in pairwise(word):
            x = ord(x) - ord('A')
            y = ord(y) - ord('A')
            dis_x = dis[x]
            for another_finger in range(26):
                nf[another_finger] = min(f[another_finger] + dis_x[y], f[y] + dis_x[another_finger])
            f, nf = nf, f
        return min(f)

###java

class Solution {
    private static final int[][] dis = new int[26][26];

    static {
        final int COLUMN = 6;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
            }
        }
    }

    public int minimumDistance(String word) {
        char[] s = word.toCharArray();

        int[] f = new int[26];
        int[] nf = new int[26];

        for (int i = 0; i < s.length - 1; i++) {
            int x = s[i] - 'A';
            int y = s[i + 1] - 'A';
            for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
                nf[anotherFinger] = Math.min(f[anotherFinger] + dis[x][y], f[y] + dis[x][anotherFinger]);
            }
            int[] tmp = f;
            f = nf;
            nf = tmp;
        }

        int ans = Integer.MAX_VALUE;
        for (int res : f) {
            ans = Math.min(ans, res);
        }
        return ans;
    }
}

###cpp

int dis[26][26];

auto init = [] {
    constexpr int COLUMN = 6;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
        }
    }
    return 0;
}();

class Solution {
public:
    int minimumDistance(string word) {
        int n = word.size();
        int f[26]{}, nf[26];

        for (int i = 0; i < n - 1; i++) {
            int x = word[i] - 'A', y = word[i + 1] - 'A';
            for (int another_finger = 0; another_finger < 26; another_finger++) {
                nf[another_finger] = min(f[another_finger] + dis[x][y], f[y] + dis[x][another_finger]);
            }
            swap(f, nf);
        }

        return ranges::min(f);
    }
};

###go

var dis [26][26]int

func init() {
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}

func minimumDistance(word string) int {
var f, nf [26]int

for i := range len(word) - 1 {
x, y := word[i]-'A', word[i+1]-'A'
for anotherFinger := range 26 {
nf[anotherFinger] = min(f[anotherFinger]+dis[x][y], f[y]+dis[x][anotherFinger])
}
f, nf = nf, f
}

return slices.Min(f[:])
}

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

复杂度分析

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

• 时间复杂度：$\mathcal{O}(n|\Sigma|)$，其中 $n$ 是 $\textit{word}$ 的长度，$|\Sigma|=26$ 是字符集合的大小。
• 空间复杂度：$\mathcal{O}(|\Sigma|)$。

专题训练

见下面动态规划题单的「§7.6 多维 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

把 $i,j,k$ 画在一维数轴上，$|i-j| + |j-k| + |k-i|$ 的几何意义是这三个下标中的最左最右下标绝对差的两倍。设最左最右的下标分别为 $i$ 和 $k$，那么三元组的距离为 $2(k-i)$。

为了让 $2(k-i)$ 尽量小，按照相同元素分组，枚举同一组中的连续三个下标分别作为 $i,j,k$。

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

优化前

###py

class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        pos = defaultdict(list)
        for i, x in enumerate(nums):
            pos[x].append(i)

        ans = inf
        for p in pos.values():
            for i in range(2, len(p)):
                ans = min(ans, (p[i] - p[i - 2]) * 2)

        return -1 if ans == inf else ans

###java

class Solution {
    public int minimumDistance(int[] nums) {
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            pos.computeIfAbsent(nums[i], _ -> new ArrayList<>()).add(i);
        }

        int ans = Integer.MAX_VALUE;
        for (List<Integer> p : pos.values()) {
            for (int i = 2; i < p.size(); i++) {
                ans = Math.min(ans, (p.get(i) - p.get(i - 2)) * 2);
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

###cpp

class Solution {
public:
    int minimumDistance(vector<int>& nums) {
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < nums.size(); i++) {
            pos[nums[i]].push_back(i);
        }

        int ans = INT_MAX;
        for (auto& [_, p] : pos) {
            for (int i = 2; i < p.size(); i++) {
                ans = min(ans, (p[i] - p[i - 2]) * 2);
            }
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

###go

func minimumDistance(nums []int) int {
pos := map[int][]int{}
for i, x := range nums {
pos[x] = append(pos[x], i)
}

ans := math.MaxInt
for _, p := range pos {
for i := 2; i < len(p); i++ {
ans = min(ans, (p[i]-p[i-2])*2)
}
}

if ans == math.MaxInt {
return -1
}
return ans
}

优化

针对本题：

1. 由于 $\textit{nums}[i]$ 的范围是 $[1,n]$，哈希表可以换成更轻量的数组。
2. 由于只关心最近的三个位置，所以只需要知道 $x = \textit{nums}[i]$ 上一次出现的位置 $\textit{last}[x]$ 和上上一次出现的位置 $\textit{last}_2[x]$。
3. 此外，不需要每次循环都计算一次乘二，乘二可以放在返回答案的时候计算。

###py

class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        n = len(nums)
        last = [-inf] * (n + 1)
        last2 = [-inf] * (n + 1)

        ans = n
        for i, x in enumerate(nums):
            ans = min(ans, i - last2[x])
            last2[x] = last[x]
            last[x] = i

        return -1 if ans == n else ans * 2

###java

class Solution {
    public int minimumDistance(int[] nums) {
        int n = nums.length;
        int[] last = new int[n + 1];
        int[] last2 = new int[n + 1];
        Arrays.fill(last, -n);
        Arrays.fill(last2, -n); // i-(-n) >= n，不会把 ans 变小

        int ans = n;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            ans = Math.min(ans, i - last2[x]);
            last2[x] = last[x];
            last[x] = i;
        }

        return ans == n ? -1 : ans * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDistance(vector<int>& nums) {
        int n = nums.size();
        vector<int> last(n + 1, -n);
        vector<int> last2(n + 1, -n); // i-(-n) >= n，不会把 ans 变小

        int ans = n;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            ans = min(ans, i - last2[x]);
            last2[x] = last[x];
            last[x] = i;
        }

        return ans == n ? -1 : ans * 2;
    }
};

###go

func minimumDistance(nums []int) int {
n := len(nums)
last := make([]int, n+1)
last2 := make([]int, n+1)
for i := range last {
last[i] = -n
last2[i] = -n // i-(-n) >= n，不会把 ans 变小
}

ans := n
for i, x := range nums {
ans = min(ans, i-last2[x])
last2[x] = last[x]
last[x] = i
}

if ans == n {
return -1
}
return ans * 2
}

复杂度分析

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

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

本题和周赛第二题是一样的，请看 我的题解。