LeetCode 每日一题题解
三种方法：记忆化搜索 -> 递推 -> 单调队列优化（Python/Java/C++/Go）endlesscheng
2022年11月6日 12:07

三种方法：记忆化搜索 -> 递推 -> 单调队列优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2022年11月6日 12:07

一、贪心性质

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

先排序，设工厂的位置为 $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」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两种方法：从左到右遍历 / 从 start 往两侧遍历（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年4月13日 06:57

两种方法：从左到右遍历 / 从 start 往两侧遍历（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年4月13日 06:57

方法一：从左到右遍历

如果 $\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. 距离最小相等元素查询

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
教你一步步思考 DP：记忆化搜索 -> 递推 -> 空间优化（Python/Java/C++/Go）endlesscheng
2026年4月7日 10:49

教你一步步思考 DP：记忆化搜索 -> 递推 -> 空间优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年4月7日 10:49

一、分析

示例 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」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
按照相同元素分组 / 记录上上一次的出现位置（Python/Java/C++/Go）endlesscheng
2025年11月9日 12:02

按照相同元素分组 / 记录上上一次的出现位置（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年11月9日 12:02

把 $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
}

优化

针对本题：

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

###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)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

O(n) 做法（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年11月9日 12:03

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

根号分解算法（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月17日 12:54

算法一：暴力

暴力处理每个询问，把下标为 $l,l+k,l+2k,\dots$ 的数都乘以 $v$。

最坏情况每次需要 $\mathcal{O}\left(\dfrac{n}{k}\right)$ 的时间，整体 $\mathcal{O}\left(\dfrac{nq}{k}\right)$ 时间。其中 $n$ 是 $\textit{nums}$ 的长度，$q$ 是 $\textit{queries}$ 的长度。

特点：当 $k$ 比较大时，算法比较快。

算法二：差分数组（商分数组）

前置知识：差分数组

如果 $k=1$，我们可以用差分数组（准确来说叫商分数组）记录询问，然后计算商分数组的前缀积，即可得到最终的数组。

商分数组 $d$ 与差分数组的区别是，初始值每一项都是 $1$（乘法单位元）；记录询问时，$d[l]$ 乘以 $v$，$d[r+1]$ 除以 $v$，即乘以 $v$ 的逆元。关于逆元，请看模运算的世界：当加减乘除遇上取模。

对于其他 $k$ 呢？

比如 $k=3$。我们可以把所有询问分为 $k=3$ 组：

作用在下标 $0,3,6,\dots$ 上的询问。
作用在下标 $1,4,7,\dots$ 上的询问。
作用在下标 $2,5,8,\dots$ 上的询问。

比如 $l=1$，$r=9$，更新的下标是 $1,4,7$。在左端点 $1$ 处乘以 $v$，右端点 $7+k=10$ 处除以 $v$（乘以 $v$ 的逆元）。这样我们计算 $1,4,7,10,\dots$ 的前缀积，就可以正确地得到最终数组每一项要乘的数了。

这里的 $7$ 是怎么算的？我们要找 $\le r$ 的最大的 $3k+1$，或者说，要把 $r$ 减少多少。这个减少量等同于当 $l=0$，$r=8$ 时，$r$ 到 $\le r$ 的最近的 $k$ 的倍数的距离，即 $8\bmod k = 2$。一般地，更新的最大下标是 $r-(r-l)\bmod k$。再加上 $k$，得到要做商分标记的位置。

一般地，在左端点 $l$ 处乘以 $v$，右端点 $r-(r-l)\bmod k+k$ 处除以 $v$（乘以 $v$ 的逆元）。

处理每个询问只需要 $\mathcal{O}(\log M)$ 时间计算逆元，其中 $M=10^9+7$。然而，我们需要遍历 $\mathcal{O}(K)$ 个长为 $\mathcal{O}(n)$ 的商分数组，总体需要 $\mathcal{O}(nK + q\log M)$ 的时间。其中 $K$ 是 $k_i$ 的最大值。

特点：当 $K$ 比较小时，算法比较快。

「平衡」两个算法

根据这两个算法的特点，我们可以规定一个阈值 $B$：

对于 $k\ge B$ 的询问，使用算法一，即暴力计算。
对于 $k < B$ 的询问，使用算法二，即用商分数组记录询问。

总体时间复杂度为

$$
\mathcal{O}\left(\dfrac{nq}{B} + nB + q\log M\right)
$$

根据基本不等式，当 $B=\sqrt q$ 时，上式取到最小值

$$
\mathcal{O}(n\sqrt q + q\log M)
$$

足以通过本题。

优化：比如没有 $k=3$ 的询问，那么对于 $k=3$ 的商分数组，我们既不创建，也不遍历。

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

写法一

###py

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        B = isqrt(len(queries))
        diff = [None] * B

        for l, r, k, v in queries:
            if k < B:
                # 懒初始化
                if not diff[k]:
                    diff[k] = [1] * (n + k)
                diff[k][l] = diff[k][l] * v % MOD
                r = r - (r - l) % k + k
                diff[k][r] = diff[k][r] * pow(v, -1, MOD) % MOD
            else:
                for i in range(l, r + 1, k):
                    nums[i] = nums[i] * v % MOD

        for k, d in enumerate(diff):
            if not d:
                continue
            for start in range(k):
                mul_d = 1
                for i in range(start, n, k):
                    mul_d = mul_d * d[i] % MOD
                    nums[i] = nums[i] * mul_d % MOD

        return reduce(xor, nums)

###java

class Solution {
    private static final int MOD = 1_000_000_007;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int B = (int) Math.sqrt(queries.length);
        int[][] diff = new int[B][];

        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2];
            long v = q[3];
            if (k < B) {
                // 懒初始化
                if (diff[k] == null) {
                    diff[k] = new int[n + k];
                    Arrays.fill(diff[k], 1);
                }
                diff[k][l] = (int) (diff[k][l] * v % MOD);
                r = r - (r - l) % k + k;
                diff[k][r] = (int) (diff[k][r] * pow(v, MOD - 2) % MOD);
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = (int) (nums[i] * v % MOD);
                }
            }
        }

        for (int k = 0; k < B; k++) {
            int[] d = diff[k];
            if (d == null) {
                continue;
            }
            for (int start = 0; start < k; start++) {
                long mulD = 1;
                for (int i = start; i < n; i += k) {
                    mulD = mulD * d[i] % MOD;
                    nums[i] = (int) (nums[i] * mulD % MOD);
                }
            }
        }

        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }
}

###cpp

class Solution {
    const int MOD = 1'000'000'007;

    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int B = sqrt(queries.size());
        vector<vector<int>> diff(B);

        for (auto& q : queries) {
            int l = q[0], r = q[1], k = q[2];
            long long v = q[3];
            if (k < B) {
                // 懒初始化
                if (diff[k].empty()) {
                    diff[k].resize(n + k, 1);
                }
                diff[k][l] = diff[k][l] * v % MOD;
                r = r - (r - l) % k + k;
                diff[k][r] = diff[k][r] * pow(v, MOD - 2) % MOD;
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = nums[i] * v % MOD;
                }
            }
        }

        for (int k = 1; k < B; k++) {
            auto& d = diff[k];
            if (d.empty()) {
                continue;
            }
            for (int start = 0; start < k; start++) {
                long long mul_d = 1;
                for (int i = start; i < n; i += k) {
                    mul_d = mul_d * d[i] % MOD;
                    nums[i] = nums[i] * mul_d % MOD;
                }
            }
        }

        return reduce(nums.begin(), nums.end(), 0, bit_xor());
    }
};

###go

const mod = 1_000_000_007

func xorAfterQueries(nums []int, queries [][]int) (ans int) {
n := len(nums)
B := int(math.Sqrt(float64(len(queries))))
diff := make([][]int, B)

for _, q := range queries {
l, r, k, v := q[0], q[1], q[2], q[3]
if k < B {
// 懒初始化
if diff[k] == nil {
diff[k] = make([]int, n+k)
for j := range diff[k] {
diff[k][j] = 1
}
}
diff[k][l] = diff[k][l] * v % mod
r = r - (r-l)%k + k
diff[k][r] = diff[k][r] * pow(v, mod-2) % mod
} else {
for i := l; i <= r; i += k {
nums[i] = nums[i] * v % mod
}
}
}

for k, d := range diff {
if d == nil {
continue
}
for start := range k {
mulD := 1
for i := start; i < n; i += k {
mulD = mulD * d[i] % mod
nums[i] = nums[i] * mulD % mod
}
}
}

for _, x := range nums {
ans ^= x
}
return
}

func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}

写法一的优化

把懒初始化的想法进一步扩展。比如 $k=3$ 时，没有遇到 $l\bmod k=2$ 的组，那么这一组的商分数组全为 $1$，无需遍历。

用二维布尔数组记录询问是否有 $(k,l\bmod k)$。

###py

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        B = isqrt(len(queries))
        diff = [None] * B
        has = [None] * B

        for l, r, k, v in queries:
            if k < B:
                # 懒初始化
                if not diff[k]:
                    diff[k] = [1] * (n + k)
                    has[k] = [False] * k
                has[k][l % k] = True
                diff[k][l] = diff[k][l] * v % MOD
                r = r - (r - l) % k + k
                diff[k][r] = diff[k][r] * pow(v, -1, MOD) % MOD
            else:
                for i in range(l, r + 1, k):
                    nums[i] = nums[i] * v % MOD

        for k, d in enumerate(diff):
            if not d:
                continue
            for start, b in enumerate(has[k]):
                if not b:
                    continue
                mul_d = 1
                for i in range(start, n, k):
                    mul_d = mul_d * d[i] % MOD
                    nums[i] = nums[i] * mul_d % MOD

        return reduce(xor, nums)

###java

class Solution {
    private static final int MOD = 1_000_000_007;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int B = (int) Math.sqrt(queries.length);
        int[][] diff = new int[B][];
        boolean[][] has = new boolean[B][];

        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2];
            long v = q[3];
            if (k < B) {
                // 懒初始化
                if (diff[k] == null) {
                    diff[k] = new int[n + k];
                    Arrays.fill(diff[k], 1);
                    has[k] = new boolean[k];
                }
                has[k][l % k] = true;
                diff[k][l] = (int) (diff[k][l] * v % MOD);
                r = r - (r - l) % k + k;
                diff[k][r] = (int) (diff[k][r] * pow(v, MOD - 2) % MOD);
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = (int) (nums[i] * v % MOD);
                }
            }
        }

        for (int k = 0; k < B; k++) {
            int[] d = diff[k];
            if (d == null) {
                continue;
            }
            for (int start = 0; start < k; start++) {
                if (!has[k][start]) {
                    continue;
                }
                long mulD = 1;
                for (int i = start; i < n; i += k) {
                    mulD = mulD * d[i] % MOD;
                    nums[i] = (int) (nums[i] * mulD % MOD);
                }
            }
        }

        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }
}

###cpp

class Solution {
    const int MOD = 1'000'000'007;

    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int B = sqrt(queries.size());
        vector<vector<int>> diff(B);
        vector<vector<int8_t>> has(B);

        for (auto& q : queries) {
            int l = q[0], r = q[1], k = q[2];
            long long v = q[3];
            if (k < B) {
                // 懒初始化
                if (diff[k].empty()) {
                    diff[k].resize(n + k, 1);
                    has[k].resize(k);
                }
                has[k][l % k] = true;
                diff[k][l] = diff[k][l] * v % MOD;
                r = r - (r - l) % k + k;
                diff[k][r] = diff[k][r] * pow(v, MOD - 2) % MOD;
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = nums[i] * v % MOD;
                }
            }
        }

        for (int k = 1; k < B; k++) {
            auto& d = diff[k];
            if (d.empty()) {
                continue;
            }
            for (int start = 0; start < k; start++) {
                if (!has[k][start]) {
                    continue;
                }
                long long mul_d = 1;
                for (int i = start; i < n; i += k) {
                    mul_d = mul_d * d[i] % MOD;
                    nums[i] = nums[i] * mul_d % MOD;
                }
            }
        }

        return reduce(nums.begin(), nums.end(), 0, bit_xor());
    }
};

###go

const mod = 1_000_000_007

func xorAfterQueries(nums []int, queries [][]int) (ans int) {
n := len(nums)
B := int(math.Sqrt(float64(len(queries))))
diff := make([][]int, B)
has := make([][]bool, B)

for _, q := range queries {
l, r, k, v := q[0], q[1], q[2], q[3]
if k < B {
// 懒初始化
if diff[k] == nil {
diff[k] = make([]int, n+k)
for j := range diff[k] {
diff[k][j] = 1
}
has[k] = make([]bool, k)
}
has[k][l%k] = true
diff[k][l] = diff[k][l] * v % mod
r = r - (r-l)%k + k
diff[k][r] = diff[k][r] * pow(v, mod-2) % mod
} else {
for i := l; i <= r; i += k {
nums[i] = nums[i] * v % mod
}
}
}

for k, d := range diff {
if d == nil {
continue
}
for start, b := range has[k] {
if !b {
continue
}
mulD := 1
for i := start; i < n; i += k {
mulD = mulD * d[i] % mod
nums[i] = nums[i] * mulD % mod
}
}
}

for _, x := range nums {
ans ^= x
}
return
}

func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}

复杂度分析

时间复杂度：$\mathcal{O}(n\sqrt q + q\log M)$，其中 $n$ 是 $\textit{nums}$ 的长度，$q$ 是 $\textit{queries}$ 的长度，$M=10^9+7$。
空间复杂度：$\mathcal{O}(n\sqrt q)$。

写法二

把询问按照 $(k,l\bmod k)$ 分组，对于每一组计算商分。这样空间复杂度更小。

###py

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        B = isqrt(len(queries))
        groups = [[] for _ in range(B)]

        for l, r, k, v in queries:
            if k < B:
                groups[k].append((l, r, v))
            else:
                for i in range(l, r + 1, k):
                    nums[i] = nums[i] * v % MOD

        for k, g in enumerate(groups):
            if not g:
                continue

            buckets = [[] for _ in range(k)]
            for t in g:
                buckets[t[0] % k].append(t)

            for start, bucket in enumerate(buckets):
                if not bucket:
                    continue
                if len(bucket) == 1:
                    # 只有一个询问，直接暴力
                    l, r, v = bucket[0]
                    for i in range(l, r + 1, k):
                        nums[i] = nums[i] * v % MOD
                    continue

                m = (n - start - 1) // k + 1
                diff = [1] * (m + 1)
                for l, r, v in bucket:
                    diff[l // k] = diff[l // k] * v % MOD
                    r = (r - start) // k + 1
                    diff[r] = diff[r] * pow(v, -1, MOD) % MOD

                mul_d = 1
                for i in range(m):
                    mul_d = mul_d * diff[i] % MOD
                    j = start + i * k
                    nums[j] = nums[j] * mul_d % MOD

        return reduce(xor, nums)

###java

class Solution {
    private static final int MOD = 1_000_000_007;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int B = (int) Math.sqrt(queries.length);
        List<int[]>[] groups = new ArrayList[B];
        Arrays.setAll(groups, _ -> new ArrayList<>());

        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            if (k < B) {
                groups[k].add(new int[]{l, r, v});
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = (int) ((long) nums[i] * v % MOD);
                }
            }
        }

        int[] diff = new int[n + 1];
        for (int k = 1; k < B; k++) {
            List<int[]> g = groups[k];
            if (g.isEmpty()) {
                continue;
            }

            List<int[]>[] buckets = new ArrayList[k];
            Arrays.setAll(buckets, _ -> new ArrayList<>());
            for (int[] t : g) {
                buckets[t[0] % k].add(t);
            }

            for (int start = 0; start < k; start++) {
                List<int[]> bucket = buckets[start];
                if (bucket.isEmpty()) {
                    continue;
                }
                if (bucket.size() == 1) {
                    // 只有一个询问，直接暴力
                    int[] t = bucket.get(0);
                    int l = t[0], r = t[1];
                    long v = t[2];
                    for (int i = l; i <= r; i += k) {
                        nums[i] = (int) (nums[i] * v % MOD);
                    }
                    continue;
                }

                int m = (n - start - 1) / k + 1;
                Arrays.fill(diff, 0, m, 1);
                for (int[] t : bucket) {
                    int l = t[0];
                    long v = t[2];
                    diff[l / k] = (int) (diff[l / k] * v % MOD);
                    int r = (t[1] - start) / k + 1;
                    diff[r] = (int) (diff[r] * pow(v, MOD - 2) % MOD);
                }

                long mulD = 1;
                for (int i = 0; i < m; i++) {
                    mulD = mulD * diff[i] % MOD;
                    int j = start + i * k;
                    nums[j] = (int) (nums[j] * mulD % MOD);
                }
            }
        }

        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }
}

###cpp

class Solution {
    const int MOD = 1'000'000'007;

    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int B = ceil(sqrt(queries.size()));
        vector<vector<tuple<int, int, int>>> groups(B);

        for (auto& q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            if (k < B) {
                groups[k].emplace_back(l, r, v);
            } else {
                for (int i = l; i <= r; i += k) {
                    nums[i] = 1LL * nums[i] * v % MOD;
                }
            }
        }

        vector<int> diff(n + 1);
        for (int k = 1; k < B; k++) {
            auto& g = groups[k];
            if (g.empty()) {
                continue;
            }

            vector<vector<tuple<int, int, int>>> buckets(k);
            for (auto& t : g) {
                buckets[get<0>(t) % k].emplace_back(t);
            }

            for (int start = 0; start < k; start++) {
                auto& bucket = buckets[start];
                if (bucket.empty()) {
                    continue;
                }
                if (bucket.size() == 1) {
                    // 只有一个询问，直接暴力
                    auto& [l, r, v] = bucket[0];
                    for (int i = l; i <= r; i += k) {
                        nums[i] = 1LL * nums[i] * v % MOD;
                    }
                    continue;
                }

                int m = (n - start - 1) / k + 1;
                fill(diff.begin(), diff.begin() + m, 1);
                for (auto& [l, r, v] : bucket) {
                    diff[l / k] = 1LL * diff[l / k] * v % MOD;
                    r = (r - start) / k + 1;
                    diff[r] = diff[r] * pow(v, MOD - 2) % MOD;
                }

                long long mul_d = 1;
                for (int i = 0; i < m; i++) {
                    mul_d = mul_d * diff[i] % MOD;
                    int j = start + i * k;
                    nums[j] = nums[j] * mul_d % MOD;
                }
            }
        }

        return reduce(nums.begin(), nums.end(), 0, bit_xor());
    }
};

###go

const mod = 1_000_000_007

func xorAfterQueries(nums []int, queries [][]int) (ans int) {
n := len(nums)
B := int(math.Sqrt(float64(len(queries))))
type tuple struct{ l, r, v int }
groups := make([][]tuple, B)

for _, q := range queries {
l, r, k, v := q[0], q[1], q[2], q[3]
if k < B {
groups[k] = append(groups[k], tuple{l, r, v})
} else {
for i := l; i <= r; i += k {
nums[i] = nums[i] * v % mod
}
}
}

diff := make([]int, n+1)
for k, g := range groups {
if g == nil {
continue
}
buckets := make([][]tuple, k)
for _, t := range g {
buckets[t.l%k] = append(buckets[t.l%k], t)
}
for start, bucket := range buckets {
if bucket == nil {
continue
}
if len(bucket) == 1 {
// 只有一个询问，直接暴力
t := bucket[0]
for i := t.l; i <= t.r; i += k {
nums[i] = nums[i] * t.v % mod
}
continue
}

for i := range (n-start-1)/k + 1 {
diff[i] = 1
}
for _, t := range bucket {
diff[t.l/k] = diff[t.l/k] * t.v % mod
r := (t.r-start)/k + 1
diff[r] = diff[r] * pow(t.v, mod-2) % mod
}

mulD := 1
for i := range (n-start-1)/k + 1 {
mulD = mulD * diff[i] % mod
j := start + i*k
nums[j] = nums[j] * mulD % mod
}
}
}

for _, x := range nums {
ans ^= x
}
return
}

func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}

进一步优化

如果询问的前三项是一样的，就把这样的询问合并在一起。

###py

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 1_000_000_007
        prod = defaultdict(lambda: 1)
        for l, r, k, v in queries:
            t = (l, r, k)
            prod[t] = prod[t] * v % MOD

        n = len(nums)
        B = isqrt(len(prod))
        groups = [[] for _ in range(B)]

        for (l, r, k), v in prod.items():
            if k < B:
                groups[k].append((l, r, v))
            else:
                for i in range(l, r + 1, k):
                    nums[i] = nums[i] * v % MOD

        for k, g in enumerate(groups):
            if not g:
                continue

            buckets = [[] for _ in range(k)]
            for t in g:
                buckets[t[0] % k].append(t)

            for start, bucket in enumerate(buckets):
                if not bucket:
                    continue
                if len(bucket) == 1:
                    # 只有一个询问，直接暴力
                    l, r, v = bucket[0]
                    for i in range(l, r + 1, k):
                        nums[i] = nums[i] * v % MOD
                    continue

                m = (n - start - 1) // k + 1
                diff = [1] * (m + 1)
                for l, r, v in bucket:
                    diff[l // k] = diff[l // k] * v % MOD
                    r = (r - start) // k + 1
                    diff[r] = diff[r] * pow(v, -1, MOD) % MOD

                mul_d = 1
                for i in range(m):
                    mul_d = mul_d * diff[i] % MOD
                    j = start + i * k
                    nums[j] = nums[j] * mul_d % MOD

        return reduce(xor, nums)

复杂度分析

时间复杂度：$\mathcal{O}(n\sqrt q + q\log M)$，其中 $n$ 是 $\textit{nums}$ 的长度，$q$ 是 $\textit{queries}$ 的长度，$M=10^9+7$。
空间复杂度：$\mathcal{O}(n + q)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

非暴力做法（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月17日 12:55

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

LeetCode 每日一题题解
分类讨论，O(1) 时间复杂度（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2021年11月14日 08:20

分类讨论，O(1) 时间复杂度（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2021年11月14日 08:20

本文把 $\textit{width}$ 简称为 $w$，把 $\textit{height}$ 简称为 $h$。

根据题意，机器人只能在网格图的最外圈中移动，移动一整圈需要 $2(w+h-2)$ 步。

设当前移动的总步数模 $2(w+h-2)$ 的结果为 $s$。分类讨论：

如果 $s < w$，机器人往右走了 $s$ 步，位于 $(s,0)$，面朝东。
如果 $w\le s < w+h-1$，机器人先往右走 $w-1$ 步，再往北走 $s-(w-1)$ 步，位于 $(w-1,s-w+1)$，面朝北。
如果 $w+h-1\le s < 2w+h-2$，机器人先往右走 $w-1$ 步，再往北走 $h-1$ 步，到达右上角 $(w-1,h-1)$，再往西走 $s-(w-1)-(h-1)$ 步，位于 $(w-1-(s-(w-1)-(h-1)),h-1) = (2w + h - s - 3,h-1)$，面朝西。
否则，机器人先往右走 $w-1$ 步，再往北走 $h-1$ 步，再往西走 $w-1$ 步，到达左上角 $(0,h-1)$，再往南走 $s-2(w-1)-(h-1)$ 步，位于 $(0,h-1-(s-2(w-1)-(h-1))) = (0, 2(w+h)-s-4)$，面朝南。

⚠注意：总步数为 $0$ 时，机器人面朝东，但总步数为 $2(w+h-2)$ 的正整数倍时，机器人面朝南。需要特判总步数为 $0$ 的特殊情况吗？不需要，当总步数大于 $0$ 时，我们可以把取模后的范围从 $[0, 2(w+h-2)-1]$ 调整到 $[1, 2(w+h-2)]$，从而使原先模为 $0$ 的总步数变成 $2(w+h-2)$，落入面朝南的分支中，这样就可以避免特判了。

class Robot:
    def __init__(self, width: int, height: int) -> None:
        self.w = width
        self.h = height
        self.s = 0

    def step(self, num: int) -> None:
        # 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        # 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        self.s = (self.s + num - 1) % ((self.w + self.h - 2) * 2) + 1

    def _getState(self) -> Tuple[int, int, str]:
        w, h, s = self.w, self.h, self.s
        if s < w:
            return s, 0, "East"
        if s < w + h - 1:
            return w - 1, s - w + 1, "North"
        if s < w * 2 + h - 2:
            return w * 2 + h - s - 3, h - 1, "West"
        return 0, (w + h) * 2 - s - 4, "South"

    def getPos(self) -> List[int]:
        x, y, _ = self._getState()
        return [x, y]

    def getDir(self) -> str:
        return self._getState()[2]

class Robot {
    private int w, h, s;

    public Robot(int width, int height) {
        w = width;
        h = height;
        s = 0;
    }

    public void step(int num) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        s = (s + num - 1) % ((w + h - 2) * 2) + 1;
    }

    public int[] getPos() {
        Object[] t = getState();
        return new int[]{(int) t[0], (int) t[1]};
    }

    public String getDir() {
        Object[] t = getState();
        return (String) t[2];
    }

    private Object[] getState() {
        if (s < w) {
            return new Object[]{s, 0, "East"};
        } else if (s < w + h - 1) {
            return new Object[]{w - 1, s - w + 1, "North"};
        } else if (s < w * 2 + h - 2) {
            return new Object[]{w * 2 + h - s - 3, h - 1, "West"};
        } else {
            return new Object[]{0, (w + h) * 2 - s - 4, "South"};
        }
    }
}

class Robot {
    int w;
    int h;
    int s = 0;

    tuple<int, int, string> getState() {
        if (s < w) {
            return {s, 0, "East"};
        } else if (s < w + h - 1) {
            return {w - 1, s - w + 1, "North"};
        } else if (s < w * 2 + h - 2) {
            return {w * 2 + h - s - 3, h - 1, "West"};
        } else {
            return {0, (w + h) * 2 - s - 4, "South"};
        }
    }

public:
    Robot(int width, int height) : w(width), h(height) {}

    void step(int num) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        s = (s + num - 1) % ((w + h - 2) * 2) + 1;
    }

    vector<int> getPos() {
        auto [x, y, _] = getState();
        return {x, y};
    }

    string getDir() {
        return get<2>(getState());
    }
};

typedef struct {
    int w;
    int h;
    int s;
} Robot;

Robot* robotCreate(int width, int height) {
    Robot* r = malloc(sizeof(Robot));
    r->w = width;
    r->h = height;
    r->s = 0;
    return r;
}

void robotStep(Robot* r, int num) {
    // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
    // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
    r->s = (r->s + num - 1) % ((r->w + r->h - 2) * 2) + 1;
}

int* robotGetPos(Robot* r, int* returnSize) {
    int w = r->w, h = r->h, s = r->s;
    int x, y;
    if (s < w) {
        x = s;
        y = 0;
    } else if (s < w + h - 1) {
        x = w - 1;
        y = s - w + 1;
    } else if (s < w * 2 + h - 2) {
        x = w * 2 + h - s - 3;
        y = h - 1;
    } else {
        x = 0;
        y = (w + h) * 2 - s - 4;
    }

    int* ans = malloc(2 * sizeof(int));
    *returnSize = 2;
    ans[0] = x;
    ans[1] = y;
    return ans;
}

char* robotGetDir(Robot* r) {
    int w = r->w, h = r->h, s = r->s;
    if (s < w) {
        return "East";
    } else if (s < w + h - 1) {
        return "North";
    } else if (s < w * 2 + h - 2) {
        return "West";
    } else {
        return "South";
    }
}

void robotFree(Robot* r) {
    free(r);
}

type Robot struct {
w, h, step int
}

func Constructor(width, height int) Robot {
return Robot{width, height, 0}
}

func (r *Robot) Step(num int) {
// 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
// 把 step 取模调整到 [1, (w+h-2)*2]，这样不需要特判 step == 0 时的方向
r.step = (r.step+num-1)%((r.w+r.h-2)*2) + 1
}

func (r *Robot) getState() (x, y int, dir string) {
w, h, step := r.w, r.h, r.step
switch {
case step < w:
return step, 0, "East"
case step < w+h-1:
return w - 1, step - w + 1, "North"
case step < w*2+h-2:
return w*2 + h - step - 3, h - 1, "West"
default:
return 0, (w+h)*2 - step - 4, "South"
}
}

func (r *Robot) GetPos() []int {
x, y, _ := r.getState()
return []int{x, y}
}

func (r *Robot) GetDir() string {
_, _, d := r.getState()
return d
}

var Robot = function(width, height) {
    this.w = width;
    this.h = height;
    this.s = 0;
};

Robot.prototype.step = function(num) {
    // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
    // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s === 0 时的方向
    this.s = (this.s + num - 1) % ((this.w + this.h - 2) * 2) + 1;
};

Robot.prototype.getState = function() {
    const w = this.w, h = this.h, s = this.s;
    if (s < w) {
        return [s, 0, "East"];
    } else if (s < w + h - 1) {
        return [w - 1, s - w + 1, "North"];
    } else if (s < w * 2 + h - 2) {
        return [w * 2 + h - s - 3, h - 1, "West"];
    } else {
        return [0, (w + h) * 2 - s - 4, "South"];
    }
};

Robot.prototype.getPos = function() {
    const [x, y, _] = this.getState();
    return [x, y];
};

Robot.prototype.getDir = function() {
    return this.getState()[2];
};

struct Robot {
    w: i32,
    h: i32,
    s: i32,
}

impl Robot {
    fn new(width: i32, height: i32) -> Self {
        Self { w: width, h: height, s: 0 }
    }

    fn step(&mut self, num: i32) {
        // 由于机器人只能走外圈，那么走 (w+h-2)*2 步后会回到起点
        // 把 s 取模调整到 [1, (w+h-2)*2]，这样不需要特判 s == 0 时的方向
        self.s = (self.s + num - 1) % ((self.w + self.h - 2) * 2) + 1;
    }

    fn get_state(&self) -> (i32, i32, String) {
        let w = self.w;
        let h = self.h;
        let s = self.s;
        if s < w {
            (s, 0, "East".to_string())
        } else if s < w + h - 1 {
            (w - 1, s - w + 1, "North".to_string())
        } else if s < w * 2 + h - 2 {
            (w * 2 + h - s - 3, h - 1, "West".to_string())
        } else {
            (0, (w + h) * 2 - s - 4, "South".to_string())
        }
    }

    fn get_pos(&self) -> Vec<i32> {
        let (x, y, _) = self.get_state();
        vec![x, y]
    }

    fn get_dir(&self) -> String {
        let (_, _, d) = self.get_state();
        d
    }
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
利用向量数组简化代码（Python/Java/C++/Go）endlesscheng
2026年3月26日 13:44

利用向量数组简化代码（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年3月26日 13:44

总体思路：模拟机器人行走的过程。一步一步走，如果下一步是障碍物，则停止移动，继续执行下一个命令。

怎么表示机器人移动的方向？

我们可以用一个向量数组

$$
\textit{dirs} = [(0, 1), (1, 0), (0, -1), (-1, 0)]
$$

分别表示顺时针的上右下左（北东南西）四个方向。

用一个下标 $k$ 表示当前机器人的方向为 $\textit{dirs}[k]$，初始 $k=0$，表示初始方向为上。

右转：也就是顺时针转 $90^\circ$，把 $k$ 增加一。如果 $k=4$，则绕回到 $\textit{dirs}$ 数组的最左边，即 $k$ 更新为 $0$。我们可以把 $k$ 统一更新为 $(k+1)\bmod 4$，这样可以兼容 $k=3$ 加一后变成 $0$ 的情况。
左转：也就是逆时针转 $90^\circ$，把 $k$ 减少一。如果 $k=0$，则绕回到 $\textit{dirs}$ 数组的最右边，即 $k$ 更新为 $3$。我们可以把 $k$ 统一更新为 $(k+3)\bmod 4$，这是因为 $\textit{dirs}$ 是个循环数组，一个元素的左边相邻元素，相当于往右数 $3$ 个元素。比如 $\textit{dirs}$ 中的 $(1,0)$ 往右数 $3$ 个元素，就是 $(0,1)$。

设 $c = \textit{commands}[i]$。当 $c>0$ 时，机器人要往 $\textit{dirs}[k]$ 方向移动 $c$ 个单位长度。一步一步移动，如果发现下一步是障碍物，则停止移动，继续执行下一个命令。

为了快速判断某个坐标是否为障碍物（是否在 $\textit{obstacles}$ 数组中），我们可以把 $\textit{obstacles}$ 转成哈希集合，判断坐标是否在哈希集合中。

注：可能起点也有障碍物，这相当于机器人站在障碍物上，是可以继续移动的。

写法一

###py

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 上右下左（顺时针）

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        obstacle_set = set(map(tuple, obstacles))
        ans = x = y = k = 0
        for c in commands:
            if c == -1:  # 右转
                k = (k + 1) % 4
            elif c == -2:  # 左转
                k = (k + 3) % 4
            else:  # 直行
                while c > 0 and (x + DIRS[k][0], y + DIRS[k][1]) not in obstacle_set:
                    x += DIRS[k][0]
                    y += DIRS[k][1]
                    c -= 1
                ans = max(ans, x * x + y * y)
        return ans

###java

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

    public int robotSim(int[] commands, int[][] obstacles) {
        HashSet<Integer> obstacleSet = new HashSet<>(obstacles.length, 1); // 预分配空间
        final int OFFSET = (int) 3e4;
        for (int[] p : obstacles) {
            // p 是两个 16 位整数，合并成一个 32 位整数
            obstacleSet.add((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
        }

        int x = 0;
        int y = 0;
        int k = 0;
        int ans = 0;
        for (int c : commands) {
            if (c == -1) { // 右转
                k = (k + 1) % 4;
            } else if (c == -2) { // 左转
                k = (k + 3) % 4;
            } else { // 直行
                while (c-- > 0) {
                    int nx = x + DIRS[k][0];
                    int ny = y + DIRS[k][1];
                    if (obstacleSet.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                }
                ans = Math.max(ans, x * x + y * y);
            }
        }
        return ans;
    }
}

###cpp

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

public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        unordered_set<int> obstacle_set;
        obstacle_set.reserve(obstacles.size()); // 预分配空间
        constexpr int OFFSET = 3e4;
        for (auto& p : obstacles) {
            // p 是两个 16 位整数，合并成一个 32 位整数
            obstacle_set.insert((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
        }

        int ans = 0, x = 0, y = 0, k = 0;
        for (int c : commands) {
            if (c == -1) { // 右转
                k = (k + 1) % 4;
            } else if (c == -2) { // 左转
                k = (k + 3) % 4;
            } else { // 直行
                while (c--) {
                    int nx = x + DIRS[k][0];
                    int ny = y + DIRS[k][1];
                    if (obstacle_set.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                }
                ans = max(ans, x * x + y * y);
            }
        }
        return ans;
    }
};

###go

type pair struct{ x, y int }
var dirs = [...]pair{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 上右下左（顺时针）

func robotSim(commands []int, obstacles [][]int) (ans int) {
isObstacle := make(map[pair]bool, len(obstacles)) // 预分配空间
for _, p := range obstacles {
isObstacle[pair{p[0], p[1]}] = true
}

x, y, k := 0, 0, 0
for _, c := range commands {
if c == -1 { // 右转
k = (k + 1) % 4
} else if c == -2 { // 左转
k = (k + 3) % 4
} else { // 直行
for ; c > 0 && !isObstacle[pair{x + dirs[k].x, y + dirs[k].y}]; c-- {
x += dirs[k].x
y += dirs[k].y
}
ans = max(ans, x*x+y*y)
}
}
return
}

写法二

设 $c = \textit{commands}[i]$。

右转时 $c=-1$，我们把 $k$ 增加了 $2c+3 = 1$。
左转时 $c=-2$，我们把 $k$ 增加了 $2c+3 = -1$。

因此，这两种情况可以进一步统一成，把 $k$ 更新成 $(k + 2c + 3)\bmod 4$。但是，当 $k=0$ 且 $2c+3=-1$ 时，$k + 2c + 3=-1$ 是负数。对于模 $4$ 运算，多增加 $4$ 不影响结果，所以可以把 $2c+3$ 改成 $2c+7$，也就把 $k$ 更新成

$$
(k + 2c + 7)\bmod 4
$$

###py

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 上右下左（顺时针）

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        obstacle_set = set(map(tuple, obstacles))
        ans = x = y = k = 0
        for c in commands:
            if c < 0:
                k = (k + c * 2 + 7) % 4  # c=-2 左转，c=-1 右转
                continue
            while c > 0 and (x + DIRS[k][0], y + DIRS[k][1]) not in obstacle_set:
                x += DIRS[k][0]
                y += DIRS[k][1]
                c -= 1
            ans = max(ans, x * x + y * y)
        return ans

###java

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

    public int robotSim(int[] commands, int[][] obstacles) {
        HashSet<Integer> obstacleSet = new HashSet<>(obstacles.length, 1); // 预分配空间
        final int OFFSET = (int) 3e4;
        for (int[] p : obstacles) {
            // p 是两个 16 位整数，合并成一个 32 位整数
            obstacleSet.add((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
        }

        int x = 0;
        int y = 0;
        int k = 0;
        int ans = 0;
        for (int c : commands) {
            if (c < 0) {
                k = (k + c * 2 + 7) % 4; // c=-2 左转，c=-1 右转
                continue;
            }
            while (c-- > 0) {
                int nx = x + DIRS[k][0];
                int ny = y + DIRS[k][1];
                if (obstacleSet.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
                    break;
                }
                x = nx;
                y = ny;
            }
            ans = Math.max(ans, x * x + y * y);
        }
        return ans;
    }
}

###cpp

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

public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        unordered_set<int> obstacle_set;
        obstacle_set.reserve(obstacles.size()); // 预分配空间
        constexpr int OFFSET = 3e4;
        for (auto& p : obstacles) {
            // p 是两个 16 位整数，合并成一个 32 位整数
            obstacle_set.insert((p[0] + OFFSET) << 16 | (p[1] + OFFSET));
        }

        int ans = 0, x = 0, y = 0, k = 0;
        for (int c : commands) {
            if (c < 0) {
                k = (k + c * 2 + 7) % 4; // c=-2 左转，c=-1 右转
                continue;
            }
            while (c--) {
                int nx = x + DIRS[k][0];
                int ny = y + DIRS[k][1];
                if (obstacle_set.contains((nx + OFFSET) << 16 | (ny + OFFSET))) {
                    break;
                }
                x = nx;
                y = ny;
            }
            ans = max(ans, x * x + y * y);
        }
        return ans;
    }
};

###go

type pair struct{ x, y int }
var dirs = [...]pair{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 上右下左（顺时针）

func robotSim(commands []int, obstacles [][]int) (ans int) {
isObstacle := make(map[pair]bool, len(obstacles)) // 预分配空间
for _, p := range obstacles {
isObstacle[pair{p[0], p[1]}] = true
}

x, y, k := 0, 0, 0
for _, c := range commands {
if c < 0 {
k = (k + c*2 + 7) % 4 // c=-2 左转，c=-1 右转
continue
}
for ; c > 0 && !isObstacle[pair{x + dirs[k].x, y + dirs[k].y}]; c-- {
x += dirs[k].x
y += dirs[k].y
}
ans = max(ans, x*x+y*y)
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(nU + m)$，其中 $n$ 是 $\textit{commands}$ 的长度，$m$ 是 $\textit{obstacles}$ 的长度，$U=\max(\textit{commands})\le 9$。
空间复杂度：$\mathcal{O}(m)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
简单题，简单做（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年3月24日 09:43

简单题，简单做（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年3月24日 09:43

机器人的横坐标，等于向右移动的次数，减去向左移动的次数。如果 $\texttt{R}$ 的个数等于 $\texttt{L}$ 的个数，那么最终横坐标为 $0$。

机器人的纵坐标，等于向上移动的次数，减去向下移动的次数。如果 $\texttt{U}$ 的个数等于 $\texttt{D}$ 的个数，那么最终纵坐标为 $0$。

这两个条件同时成立，才能回到原点。

###py

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        return moves.count('R') == moves.count('L') and \
               moves.count('U') == moves.count('D')

###py

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        cnt = Counter(moves)
        return cnt['R'] == cnt['L'] and cnt['U'] == cnt['D']

###java

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for (char move : moves.toCharArray()) {
            if (move == 'R') {
                x++;
            } else if (move == 'L') {
                x--;
            } else if (move == 'U') {
                y++;
            } else {
                y--;
            }
        }
        return x == 0 && y == 0;
    }
}

###cpp

class Solution {
public:
    bool judgeCircle(string moves) {
        return ranges::count(moves, 'R') == ranges::count(moves, 'L') &&
               ranges::count(moves, 'U') == ranges::count(moves, 'D');
    }
};

###c

bool judgeCircle(char* moves) {
    int x = 0, y = 0;
    for (int i = 0; moves[i]; i++) {
        char move = moves[i];
        if (move == 'R') {
            x++;
        } else if (move == 'L') {
            x--;
        } else if (move == 'U') {
            y++;
        } else {
            y--;
        }
    }
    return x == 0 && y == 0;
}

###go

func judgeCircle(moves string) bool {
    return strings.Count(moves, "R") == strings.Count(moves, "L") &&
           strings.Count(moves, "U") == strings.Count(moves, "D")
}

###js

var judgeCircle = function(moves) {
    const cnt = _.countBy(moves);
    return cnt['R'] === cnt['L'] && cnt['U'] === cnt['D'];
};

###rust

impl Solution {
    pub fn judge_circle(moves: String) -> bool {
        moves.matches('R').count() == moves.matches('L').count() &&
        moves.matches('U').count() == moves.matches('D').count()
    }
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
脑筋急转弯（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2021年11月28日 00:10

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

LeetCode 每日一题题解

作者 endlesscheng

2021年11月28日 00:10

脑筋急转弯：由于题目保证代价均为非负数，所以除了径直走以外，其它弯弯绕绕的策略都不可能更优，那么直接统计径直走的代价即可。

设起点为 $(x_0,y_0)$，终点为 $(x_1,y_1)$。

分别计算上下移动的代价，左右移动的代价，二者之和就是总代价。

上下移动的代价：如果 $x_0 < x_1$，那么从起点移动到终点，$x_0+1,x_0+2,\ldots,x_1$ 这些行都要访问到，移动代价为 $\textit{rowCosts}$ 的子数组 $[x_0+1,x_1]$ 的元素和。如果 $x_0 > x_1$，那么移动代价为 $\textit{rowCosts}$ 的子数组 $[x_1+1,x_0]$ 的元素和。
左右移动的代价：如果 $y_0 < y_1$，那么从起点移动到终点，$y_0+1,y_0+2,\ldots,y_1$ 这些列都要访问到，移动代价为 $\textit{colCosts}$ 的子数组 $[y_0+1,y_1]$ 的元素和。如果 $y_0 > y_1$，那么移动代价为 $\textit{colCosts}$ 的子数组 $[y_1+1,y_0]$ 的元素和。

代码实现时，不需要根据 $x_0$ 和 $x_1$ 的大小关系分情况讨论，而是计算 $\textit{rowCosts}$ 的子数组 $[\min(x_0,x_1), \max(x_0,x_1)]$ 的元素和，再减去多算的起点代价 $\textit{rowCosts}[x_0]$。对于 $y_0$ 和 $y_1$ 同理。

class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        x0, y0 = startPos
        x1, y1 = homePos

        # 起点的代价不计入，先减去
        ans = -rowCosts[x0] - colCosts[y0]

        # 累加代价（包含起点）
        ans += sum(rowCosts[min(x0, x1): max(x0, x1) + 1])
        ans += sum(colCosts[min(y0, y1): max(y0, y1) + 1])

        return ans

class Solution {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int x0 = startPos[0], y0 = startPos[1];
        int x1 = homePos[0], y1 = homePos[1];

        // 起点的代价不计入，先减去
        int ans = -rowCosts[x0] - colCosts[y0];

        // 累加代价（包含起点）
        int l1 = Math.min(x0, x1), r1 = Math.max(x0, x1);
        for (int i = l1; i <= r1; i++) {
            ans += rowCosts[i];
        }

        int l2 = Math.min(y0, y1), r2 = Math.max(y0, y1);
        for (int i = l2; i <= r2; i++) {
            ans += colCosts[i];
        }

        return ans;
    }
}

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int x0 = startPos[0], y0 = startPos[1];
        int x1 = homePos[0], y1 = homePos[1];

        // 起点的代价不计入，先减去
        int ans = -rowCosts[x0] - colCosts[y0];

        // 累加代价（包含起点）
        ans += reduce(rowCosts.begin() + min(x0, x1), rowCosts.begin() + max(x0, x1) + 1, 0);
        ans += reduce(colCosts.begin() + min(y0, y1), colCosts.begin() + max(y0, y1) + 1, 0);

        return ans;
    }
};

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

int minCost(int* startPos, int startPosSize, int* homePos, int homePosSize, int* rowCosts, int rowCostsSize, int* colCosts, int colCostsSize) {
    int x0 = startPos[0], y0 = startPos[1];
    int x1 = homePos[0], y1 = homePos[1];

    // 起点的代价不计入，先减去
    int ans = -rowCosts[x0] - colCosts[y0];

    // 累加代价（包含起点）
    int l1 = MIN(x0, x1), r1 = MAX(x0, x1);
    for (int i = l1; i <= r1; i++) {
        ans += rowCosts[i];
    }

    int l2 = MIN(y0, y1), r2 = MAX(y0, y1);
    for (int i = l2; i <= r2; i++) {
        ans += colCosts[i];
    }

    return ans;
}

func minCost(startPos, homePos, rowCosts, colCosts []int) int {
x0, y0 := startPos[0], startPos[1]
x1, y1 := homePos[0], homePos[1]

// 起点的代价不计入，先减去
ans := -rowCosts[x0] - colCosts[y0]

// 累加代价（包含起点）
for _, cost := range rowCosts[min(x0, x1) : max(x0, x1)+1] {
ans += cost
}
for _, cost := range colCosts[min(y0, y1) : max(y0, y1)+1] {
ans += cost
}

return ans
}

var minCost = function(startPos, homePos, rowCosts, colCosts) {
    const [x0, y0] = startPos;
    const [x1, y1] = homePos;

    // 起点的代价不计入，先减去
    let ans = -rowCosts[x0] - colCosts[y0];

    // 累加代价（包含起点）
    ans += _.sum(rowCosts.slice(Math.min(x0, x1), Math.max(x0, x1) + 1));
    ans += _.sum(colCosts.slice(Math.min(y0, y1), Math.max(y0, y1) + 1));

    return ans;
};

impl Solution {
    pub fn min_cost(start_pos: Vec<i32>, home_pos: Vec<i32>, row_costs: Vec<i32>, col_costs: Vec<i32>) -> i32 {
        let x0 = start_pos[0] as usize;
        let y0 = start_pos[1] as usize;
        let x1 = home_pos[0] as usize;
        let y1 = home_pos[1] as usize;

        // 起点的代价不计入，先减去
        let mut ans = -row_costs[x0] - col_costs[y0];

        // 累加代价（包含起点）
        ans += row_costs[x0.min(x1)..=x0.max(x1)].iter().sum::<i32>();
        ans += col_costs[y0.min(y1)..=y0.max(y1)].iter().sum::<i32>();

        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(|\textit{start}{\textit{row}} - \textit{home}{\textit{row}}| + |\textit{start}{\textit{col}} - \textit{home}{\textit{col}}|)$。
空间复杂度：$\mathcal{O}(1)$。Python 和 JS 把切片改成普通循环即可做到 $\mathcal{O}(1)$ 空间。

如果有负数代价呢？

本题是图论中的最短路问题。在有负数边权的情况下，可以用 Bellman-Ford 算法解决。需要注意的是，如果有负环，则最小代价为 $-\infty$。

专题训练

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
教你一步步思考 DP：从记忆化搜索到递推到双指针优化（Python/Java/C++/Go）endlesscheng
2025年8月24日 12:54

教你一步步思考 DP：从记忆化搜索到递推到双指针优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月24日 12:54

一、寻找子问题

先把机器人和墙壁从小到大排序。

考虑最右边的机器人。分类讨论：

如果它往左射击，那么需要解决的子问题为：对于前 $n-1$ 个机器人，在第 $n$ 个机器人往左射击的前提下，能摧毁的最大墙壁数量。
如果它往右射击，那么需要解决的子问题为：对于前 $n-1$ 个机器人，在第 $n$ 个机器人往右射击的前提下，能摧毁的最大墙壁数量。

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

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

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

根据上面的讨论，定义状态为 $\textit{dfs}(i,j)$，表示对于（排序后）下标在 $[0,i]$ 中的机器人，在机器人 $i+1$ 往左/右射击的前提下，能摧毁的最大墙壁数量。其中 $j=0$ 表示机器人 $i+1$ 往左射击，$j=1$ 表示机器人 $i+1$ 往右射击。

考虑机器人 $i$ 往哪个方向射击：

往左，那么接下来要解决的问题是，下标在 $[0,i-1]$ 中的机器人，在机器人 $i$ 往左射击的前提下，能摧毁的最大墙壁数量。即 $\textit{dfs}(i-1,0)$。然后加上机器人 $i$ 摧毁的墙壁数量。
- 往左最远为 $\textit{leftX} = \max(x_i - d_i,x_{i-1}+1)$，其中 $x_i$ 和 $d_i$ 分别表示机器人 $i$ 的位置和射击距离。为避免重复计算，我们规定，往左不能到达机器人 $i-1$。
- 在 $\textit{walls}$ 中二分查找 $\ge \textit{leftX}$ 的第一个数的下标，记作 $\textit{left}$。
- 在 $\textit{walls}$ 中二分查找 $\le x_i$ 的最后一个数的下标加一。根据二分查找红蓝染色法【基础算法精讲 04】，转化成二分查找 $\ge x_i + 1$ 的第一个数的下标，记作 $\textit{cur}_0$。
- 那么 $[\textit{left},\textit{cur}_0-1]$ 中的墙都能摧毁，这有 $\textit{cur}_0- \textit{left}$ 个。
往右，那么接下来要解决的问题是，下标在 $[0,i-1]$ 中的机器人，在机器人 $i$ 往右射击的前提下，能摧毁的最大墙壁数量。即 $\textit{dfs}(i-1,1)$。
- 往右最远为 $\textit{rightX} = \min(x_i + d_i,x_{i+1}-1)$ 或者 $\min(x_i + d_i,x_{i+1}-d_{i+1}-1)$，取决于右边那个机器人是往右还是往左射击。
- 在 $\textit{walls}$ 中二分查找 $\le \textit{rightX}$ 的最后一个数的下标加一，即 $\ge \textit{rightX} + 1$ 的第一个数的下标，记作 $\textit{right}$。
- 在 $\textit{walls}$ 中二分查找 $\ge x_i$ 的第一个数的下标，记作 $\textit{cur}_1$。
- 那么 $[\textit{cur}_1,\textit{right}-1]$ 中的墙都能摧毁，这有 $\textit{right} - \textit{cur}_1$ 个。

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

$$
\textit{dfs}(i,j) = \max(\textit{dfs}(i-1,0) + \textit{cur}_0- \textit{left}, \textit{dfs}(i-1,1) + \textit{right} - \textit{cur}_1)
$$

递归边界：$\textit{dfs}(-1,j)=0$。没有机器人，无法摧毁墙壁。

递归入口：$\textit{dfs}(n-1,1)$。机器人 $n-1$ 右边没有机器人，等价于右边那个机器人往右射击。

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

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

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

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

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

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

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

优化前

###py

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        a = sorted(zip(robots, distance), key=lambda p: p[0])
        walls.sort()

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

            x, d = a[i]
            # 往左射，墙的坐标范围为 [left_x, x]
            left_x = x - d
            if i > 0:
                left_x = max(left_x, a[i - 1][0] + 1)  # +1 表示不能射到左边那个机器人
            left = bisect_left(walls, left_x)
            cur = bisect_right(walls, x)
            res_left = dfs(i - 1, 0) + cur - left  # 下标在 [left, cur-1] 中的墙都能摧毁

            # 往右射，墙的坐标范围为 [x, right_x]
            right_x = x + d
            if i + 1 < n:
                x2, d2 = a[i + 1]
                if j == 0:  # 右边那个机器人往左射
                    x2 -= d2
                right_x = min(right_x, x2 - 1)  # -1 表示不能射到右边那个机器人（或者它往左射到的墙）
            right = bisect_right(walls, right_x)
            cur = bisect_left(walls, x)
            res_right = dfs(i - 1, 1) + right - cur  # 下标在 [cur, right-1] 中的墙都能摧毁

            return max(res_left, res_right)

        return dfs(n - 1, 1)

###java

class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = robots[i];
            a[i][1] = distance[i];
        }
        Arrays.sort(a, (p, q) -> p[0] - q[0]);
        Arrays.sort(walls);

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

    private int dfs(int i, int j, int[][] a, int[] walls, int[][] memo) {
        if (i < 0) {
            return 0;
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }
      
        int x = a[i][0], d = a[i][1];
        // 往左射，墙的坐标范围为 [leftX, x]
        int leftX = x - d;
        if (i > 0) {
            leftX = Math.max(leftX, a[i - 1][0] + 1); // +1 表示不能射到左边那个机器人
        }
        int left = lowerBound(walls, leftX);
        int cur = lowerBound(walls, x + 1);
        int resLeft = dfs(i - 1, 0, a, walls, memo) + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

        // 往右射，墙的坐标范围为 [x, rightX]
        int rightX = x + d;
        if (i + 1 < a.length) {
            int x2 = a[i + 1][0];
            if (j == 0) { // 右边那个机器人往左射
                x2 -= a[i + 1][1];
            }
            rightX = Math.min(rightX, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
        }
        int right = lowerBound(walls, rightX + 1);
        cur = lowerBound(walls, x);
        int resRight = dfs(i - 1, 1, a, walls, memo) + right - cur; // 下标在 [cur, right-1] 中的墙都能摧毁

        return memo[i][j] = Math.max(resLeft, resRight); // 记忆化
    }

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

###cpp

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        struct Pair { int x, d; };
        vector<Pair> a(n);
        for (int i = 0; i < n; i++) {
            a[i] = {robots[i], distance[i]};
        }
        ranges::sort(a, {}, &Pair::x);
        ranges::sort(walls);

        vector memo(n, array<int, 2>{-1, -1}); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0) {
                return 0;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            
            auto [x, d] = a[i];
            // 往左射，墙的坐标范围为 [left_x, x]
            int left_x = x - d;
            if (i > 0) {
                left_x = max(left_x, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
            }
            int left = ranges::lower_bound(walls, left_x) - walls.begin();
            int cur = ranges::upper_bound(walls, x) - walls.begin();
            res = dfs(i - 1, 0) + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            // 往右射，墙的坐标范围为 [x, right_x]
            int right_x = x + d;
            if (i + 1 < n) {
                auto [x2, d2] = a[i + 1];
                if (j == 0) { // 右边那个机器人往左射
                    x2 -= d2;
                }
                right_x = min(right_x, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
            }
            int right = ranges::upper_bound(walls, right_x) - walls.begin();
            cur = ranges::lower_bound(walls, x) - walls.begin();
            res = max(res, dfs(i - 1, 1) + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            return res;
        };

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

###go

func maxWalls(robots []int, distance []int, walls []int) int {
n := len(robots)
type pair struct{ x, d int }
a := make([]pair, n)
for i, x := range robots {
a[i] = pair{x, distance[i]}
}
slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
slices.Sort(walls)

memo := make([][2]int, n)
for i := range memo {
memo[i] = [2]int{-1, -1}
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if i < 0 {
return 0
}
p := &memo[i][j]
if *p != -1 {
return *p
}

// 往左射，墙的坐标范围为 [leftX, a[i].x]
leftX := a[i].x - a[i].d
if i > 0 {
leftX = max(leftX, a[i-1].x+1) // +1 表示不能射到左边那个机器人
}
left := sort.SearchInts(walls, leftX)
cur := sort.SearchInts(walls, a[i].x+1)
res := dfs(i-1, 0) + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

// 往右射，墙的坐标范围为 [a[i].x, rightX]
rightX := a[i].x + a[i].d
if i+1 < n {
x2 := a[i+1].x
if j == 0 { // 右边那个机器人往左射
x2 -= a[i+1].d
}
rightX = min(rightX, x2-1) // 不能到达右边那个机器人（或者它往左射到的墙）
}
right := sort.SearchInts(walls, rightX+1)
cur = sort.SearchInts(walls, a[i].x)
res = max(res, dfs(i-1, 1)+right-cur) // 下标在 [cur, right-1] 中的墙都能摧毁

*p = res
return res
}
return dfs(n-1, 1)
}

优化

添加两个位置分别为 $0$ 和 $\infty$ 的机器人，当作哨兵，从而简化边界的判断。

###py

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        a = [(0, 0)] + sorted(zip(robots, distance), key=lambda p: p[0]) + [(inf, 0)]
        walls.sort()

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

            x, d = a[i]
            # 往左射，墙的坐标范围为 [left_x, x]
            left_x = max(x - d, a[i - 1][0] + 1)  # +1 表示不能射到左边那个机器人
            left = bisect_left(walls, left_x)
            cur = bisect_right(walls, x)
            res_left = dfs(i - 1, 0) + cur - left  # 下标在 [left, cur-1] 中的墙都能摧毁

            # 往右射，墙的坐标范围为 [x, right_x]
            x2, d2 = a[i + 1]
            if j == 0:  # 右边那个机器人往左射
                x2 -= d2
            right_x = min(x + d, x2 - 1)  # -1 表示不能射到右边那个机器人（或者它往左射到的墙）
            right = bisect_right(walls, right_x)
            cur = bisect_left(walls, x)
            res_right = dfs(i - 1, 1) + right - cur  # 下标在 [cur, right-1] 中的墙都能摧毁

            return max(res_left, res_right)

        return dfs(n, 1)

###java

class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;
        int[][] a = new int[n + 2][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = robots[i];
            a[i][1] = distance[i];
        }
        a[n + 1][0] = Integer.MAX_VALUE;
        Arrays.sort(a, (p, q) -> p[0] - q[0]);
        Arrays.sort(walls);

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

    private int dfs(int i, int j, int[][] a, int[] walls, int[][] memo) {
        if (i == 0) {
            return 0;
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }

        int x = a[i][0], d = a[i][1];
        // 往左射，墙的坐标范围为 [leftX, x]
        int leftX = Math.max(x - d, a[i - 1][0] + 1); // +1 表示不能射到左边那个机器人
        int left = lowerBound(walls, leftX);
        int cur = lowerBound(walls, x + 1);
        int resLeft = dfs(i - 1, 0, a, walls, memo) + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

        // 往右射，墙的坐标范围为 [x, rightX]
        int x2 = a[i + 1][0];
        if (j == 0) { // 右边那个机器人往左射
            x2 -= a[i + 1][1];
        }
        int rightX = Math.min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
        int right = lowerBound(walls, rightX + 1);
        cur = lowerBound(walls, x);
        int resRight = dfs(i - 1, 1, a, walls, memo) + right - cur; // 下标在 [cur, right-1] 中的墙都能摧毁

        return memo[i][j] = Math.max(resLeft, resRight); // 记忆化
    }

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

###cpp

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        struct Pair { int x, d; };
        vector<Pair> a(n + 2);
        for (int i = 0; i < n; i++) {
            a[i] = {robots[i], distance[i]};
        }
        a[n + 1].x = INT_MAX;
        ranges::sort(a, {}, &Pair::x);
        ranges::sort(walls);

        vector memo(n + 1, array<int, 2>{-1, -1}); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i == 0) {
                return 0;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }

            auto [x, d] = a[i];
            // 往左射，墙的坐标范围为 [left_x, x]
            int left_x = max(x - d, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
            int left = ranges::lower_bound(walls, left_x) - walls.begin();
            int cur = ranges::upper_bound(walls, x) - walls.begin();
            res = dfs(i - 1, 0) + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            // 往右射，墙的坐标范围为 [x, right_x]
            auto [x2, d2] = a[i + 1];
            if (j == 0) { // 右边那个机器人往左射
                x2 -= d2;
            }
            int right_x = min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
            int right = ranges::upper_bound(walls, right_x) - walls.begin();
            cur = ranges::lower_bound(walls, x) - walls.begin();
            res = max(res, dfs(i - 1, 1) + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            return res;
        };

        return dfs(n, 1);
    }
};

###go

func maxWalls(robots []int, distance []int, walls []int) int {
n := len(robots)
type pair struct{ x, d int }
a := make([]pair, n+2)
for i, x := range robots {
a[i] = pair{x, distance[i]}
}
a[n+1].x = math.MaxInt // 哨兵
slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
slices.Sort(walls)

memo := make([][2]int, n+1)
for i := range memo {
memo[i] = [2]int{-1, -1}
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if i == 0 {
return 0
}
p := &memo[i][j]
if *p != -1 {
return *p
}

// 往左射，墙的坐标范围为 [leftX, a[i].x]
leftX := max(a[i].x-a[i].d, a[i-1].x+1) // +1 表示不能射到左边那个机器人
left := sort.SearchInts(walls, leftX)
cur := sort.SearchInts(walls, a[i].x+1)
res := dfs(i-1, 0) + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

// 往右射，墙的坐标范围为 [a[i].x, rightX]
x2 := a[i+1].x
if j == 0 { // 右边那个机器人往左射
x2 -= a[i+1].d
}
rightX := min(a[i].x+a[i].d, x2-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
right := sort.SearchInts(walls, rightX+1)
cur = sort.SearchInts(walls, a[i].x)
res = max(res, dfs(i-1, 1)+right-cur) // 下标在 [cur, right-1] 中的墙都能摧毁

*p = res
return res
}
return dfs(n, 1)
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + m\log m + n\log m)$，其中 $n$ 是 $\textit{robots}$ 的长度，$m$ 是 $\textit{walls}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n)$，单个状态的计算时间为 $\mathcal{O}(\log m)$，所以动态规划的时间复杂度为 $\mathcal{O}(n\log m)$。前面排序需要 $\mathcal{O}(n\log n + m\log m)$ 的时间。
空间复杂度：$\mathcal{O}(n)$。保存多少状态，就需要多少空间。忽略排序的栈开销。

四、1:1 翻译成递推

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

具体来说，$f[i][j]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示对于（排序，添加哨兵后的）下标在 $[1,i]$ 中的机器人，在机器人 $i+1$ 往左/右射击的前提下，能摧毁的最大墙壁数量。

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

$$
f[i][j] = \max(f[i-1][0] + \textit{cur}_0- \textit{left}, f[i-1][1] + \textit{right} - \textit{cur}_1)
$$

初始值 $f[0][j]=0$，翻译自（添加哨兵后的）递归边界 $\textit{dfs}(0,j)=0$。

答案为 $f[n][1]$，翻译自（添加哨兵后的）递归入口 $\textit{dfs}(n,1)$。

###py

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        a = [(0, 0)] + sorted(zip(robots, distance), key=lambda p: p[0]) + [(inf, 0)]
        walls.sort()

        f = [[0, 0] for _ in range(n + 1)]
        for i in range(1, n + 1):
            x, d = a[i]

            # 往左射，墙的坐标范围为 [left_x, x]
            left_x = max(x - d, a[i - 1][0] + 1)  # +1 表示不能射到左边那个机器人
            left = bisect_left(walls, left_x)
            cur = bisect_right(walls, x)
            left_res = f[i - 1][0] + cur - left  # 下标在 [left, cur-1] 中的墙都能摧毁

            cur = bisect_left(walls, x)
            for j in range(2):
                # 往右射，墙的坐标范围为 [x, right_x]
                x2, d2 = a[i + 1]
                if j == 0:  # 右边那个机器人往左射
                    x2 -= d2
                right_x = min(x + d, x2 - 1)  # -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                right = bisect_right(walls, right_x)
                f[i][j] = max(left_res, f[i - 1][1] + right - cur)  # 下标在 [cur, right-1] 中的墙都能摧毁
        return f[n][1]

###java

class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;
        int[][] a = new int[n + 2][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = robots[i];
            a[i][1] = distance[i];
        }
        a[n + 1][0] = Integer.MAX_VALUE;
        Arrays.sort(a, (p, q) -> p[0] - q[0]);
        Arrays.sort(walls);

        int[][] f = new int[n + 1][2];
        for (int i = 1; i <= n; i++) {
            int x = a[i][0], d = a[i][1];

            // 往左射，墙的坐标范围为 [leftX, x]
            int leftX = Math.max(x - d, a[i - 1][0] + 1); // +1 表示不能射到左边那个机器人
            int left = lowerBound(walls, leftX);
            int cur = lowerBound(walls, x + 1);
            int leftRes = f[i - 1][0] + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            cur = lowerBound(walls, x);
            for (int j = 0; j < 2; j++) {
                // 往右射，墙的坐标范围为 [x, rightX]
                int x2 = a[i + 1][0];
                if (j == 0) { // 右边那个机器人往左射
                    x2 -= a[i + 1][1];
                }
                int rightX = Math.min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                int right = lowerBound(walls, rightX + 1);
                f[i][j] = Math.max(leftRes, f[i - 1][1] + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            }
        }
        return f[n][1];
    }

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

###cpp

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        struct Pair { int x, d; };
        vector<Pair> a(n + 2);
        for (int i = 0; i < n; i++) {
            a[i] = {robots[i], distance[i]};
        }
        a[n + 1].x = INT_MAX;
        ranges::sort(a, {}, &Pair::x);
        ranges::sort(walls);

        vector<array<int, 2>> f(n + 1);
        for (int i = 1; i <= n; i++) {
            auto [x, d] = a[i];

            // 往左射，墙的坐标范围为 [left_x, x]
            int left_x = max(x - d, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
            int left = ranges::lower_bound(walls, left_x) - walls.begin();
            int cur = ranges::upper_bound(walls, x) - walls.begin();
            int left_res = f[i - 1][0] + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            cur = ranges::lower_bound(walls, x) - walls.begin();
            for (int j = 0; j < 2; j++) {
                // 往右射，墙的坐标范围为 [x, right_x]
                auto [x2, d2] = a[i + 1];
                if (j == 0) { // 右边那个机器人往左射
                    x2 -= d2;
                }
                int right_x = min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                int right = ranges::upper_bound(walls, right_x) - walls.begin();
                f[i][j] = max(left_res, f[i - 1][1] + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            }
        }
        return f[n][1];
    }
};

###go

func maxWalls(robots []int, distance []int, walls []int) int {
n := len(robots)
type pair struct{ x, d int }
a := make([]pair, n+2)
for i, x := range robots {
a[i] = pair{x, distance[i]}
}
a[n+1].x = math.MaxInt // 哨兵
slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
slices.Sort(walls)

f := make([][2]int, n+1)
for i := 1; i <= n; i++ {
p := a[i]

// 往左射，墙的坐标范围为 [leftX, p.x]
leftX := max(p.x-p.d, a[i-1].x+1) // +1 表示不能射到左边那个机器人
left := sort.SearchInts(walls, leftX)
cur := sort.SearchInts(walls, p.x+1)
leftRes := f[i-1][0] + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

cur = sort.SearchInts(walls, p.x)
for j := range 2 {
// 往右射，墙的坐标范围为 [p.x, rightX]
x2 := a[i+1].x
if j == 0 { // 右边那个机器人往左射
x2 -= a[i+1].d
}
rightX := min(p.x+p.d, x2-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
right := sort.SearchInts(walls, rightX+1)
f[i][j] = max(leftRes, f[i-1][1]+right-cur) // 下标在 [cur, right-1] 中的墙都能摧毁
}
}
return f[n][1]
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + m\log m + n\log m)$，其中 $n$ 是 $\textit{robots}$ 的长度，$m$ 是 $\textit{walls}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。忽略排序的栈开销。

五、空间优化

观察上面的状态转移方程，在计算 $f[i+1]$ 时，只会用到 $f[i]$，不会用到比 $i$ 更早的状态。

类似背包问题，去掉 $f$ 的第一个维度，把 $f[i+1]$ 和 $f[i]$ 保存到同一个数组中。

###py

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

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        a = [(0, 0)] + sorted(zip(robots, distance), key=lambda p: p[0]) + [(inf, 0)]
        walls.sort()

        f = [0, 0]
        for i in range(1, n + 1):
            x, d = a[i]

            # 往左射，墙的坐标范围为 [left_x, x]
            left_x = max(x - d, a[i - 1][0] + 1)  # +1 表示不能射到左边那个机器人
            left = bisect_left(walls, left_x)
            cur = bisect_right(walls, x)
            left_res = f[0] + cur - left  # 下标在 [left, cur-1] 中的墙都能摧毁

            cur = bisect_left(walls, x)
            for j in range(2):
                # 往右射，墙的坐标范围为 [x, right_x]
                x2, d2 = a[i + 1]
                if j == 0:  # 右边那个机器人往左射
                    x2 -= d2
                right_x = min(x + d, x2 - 1)  # -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                right = bisect_right(walls, right_x)
                f[j] = max(left_res, f[1] + right - cur)  # 下标在 [cur, right-1] 中的墙都能摧毁
        return f[1]

###java

class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;
        int[][] a = new int[n + 2][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = robots[i];
            a[i][1] = distance[i];
        }
        a[n + 1][0] = Integer.MAX_VALUE;
        Arrays.sort(a, (p, q) -> p[0] - q[0]);
        Arrays.sort(walls);

        int[] f = new int[2];
        for (int i = 1; i <= n; i++) {
            int x = a[i][0], d = a[i][1];

            // 往左射，墙的坐标范围为 [leftX, x]
            int leftX = Math.max(x - d, a[i - 1][0] + 1); // +1 表示不能射到左边那个机器人
            int left = lowerBound(walls, leftX);
            int cur = lowerBound(walls, x + 1);
            int leftRes = f[0] + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            cur = lowerBound(walls, x);
            for (int j = 0; j < 2; j++) {
                // 往右射，墙的坐标范围为 [x, rightX]
                int x2 = a[i + 1][0];
                if (j == 0) { // 右边那个机器人往左射
                    x2 -= a[i + 1][1];
                }
                int rightX = Math.min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                int right = lowerBound(walls, rightX + 1);
                f[j] = Math.max(leftRes, f[1] + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            }
        }
        return f[1];
    }

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

###cpp

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        struct Pair { int x, d; };
        vector<Pair> a(n + 2);
        for (int i = 0; i < n; i++) {
            a[i] = {robots[i], distance[i]};
        }
        a[n + 1].x = INT_MAX;
        ranges::sort(a, {}, &Pair::x);
        ranges::sort(walls);

        int f[2]{};
        for (int i = 1; i <= n; i++) {
            auto [x, d] = a[i];

            // 往左射，墙的坐标范围为 [left_x, x]
            int left_x = max(x - d, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
            int left = ranges::lower_bound(walls, left_x) - walls.begin();
            int cur = ranges::upper_bound(walls, x) - walls.begin();
            int left_res = f[0] + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            cur = ranges::lower_bound(walls, x) - walls.begin();
            for (int j = 0; j < 2; j++) {
                // 往右射，墙的坐标范围为 [x, right_x]
                auto [x2, d2] = a[i + 1];
                if (j == 0) { // 右边那个机器人往左射
                    x2 -= d2;
                }
                int right_x = min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
                int right = ranges::upper_bound(walls, right_x) - walls.begin();
                f[j] = max(left_res, f[1] + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
            }
        }
        return f[1];
    }
};

###go

func maxWalls(robots []int, distance []int, walls []int) int {
n := len(robots)
type pair struct{ x, d int }
a := make([]pair, n+2)
for i, x := range robots {
a[i] = pair{x, distance[i]}
}
a[n+1].x = math.MaxInt // 哨兵
slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
slices.Sort(walls)

f := [2]int{}
for i := 1; i <= n; i++ {
p := a[i]

// 往左射，墙的坐标范围为 [leftX, p.x]
leftX := max(p.x-p.d, a[i-1].x+1) // +1 表示不能射到左边那个机器人
left := sort.SearchInts(walls, leftX)
cur := sort.SearchInts(walls, p.x+1)
leftRes := f[0] + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

cur = sort.SearchInts(walls, p.x)
for j := range 2 {
// 往右射，墙的坐标范围为 [p.x, rightX]
x2 := a[i+1].x
if j == 0 { // 右边那个机器人往左射
x2 -= a[i+1].d
}
rightX := min(p.x+p.d, x2-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
right := sort.SearchInts(walls, rightX+1)
f[j] = max(leftRes, f[1]+right-cur) // 下标在 [cur, right-1] 中的墙都能摧毁
}
}
return f[1]
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + m\log m + n\log m)$，其中 $n$ 是 $\textit{robots}$ 的长度，$m$ 是 $\textit{walls}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。忽略排序的栈开销。

六、双指针优化

由于随着 $i$ 变大，二分查找中的 $\textit{left},\textit{cur},\textit{right}$ 也随之变大，我们可以用双指针（多指针）优化。这样算法瓶颈就在排序上了。

###py

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

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n, m = len(robots), len(walls)
        a = [(0, 0)] + sorted(zip(robots, distance), key=lambda p: p[0]) + [(inf, 0)]
        walls.sort()

        f0 = f1 = left = cur = right0 = right1 = 0
        for i in range(1, n + 1):
            x, d = a[i]

            # 往左射，墙的坐标范围为 [left_x, x]
            left_x = max(x - d, a[i - 1][0] + 1)  # +1 表示不能射到左边那个机器人
            while left < m and walls[left] < left_x:
                left += 1
            while cur < m and walls[cur] < x:
                cur += 1
            cur1 = cur
            if cur < m and walls[cur] == x:
                cur += 1
            left_res = f0 + cur - left  # 下标在 [left, cur-1] 中的墙都能摧毁

            # 往右射，右边那个机器人往左射，墙的坐标范围为 [x, right_x]
            x2, d2 = a[i + 1]
            right_x = min(x + d, x2 - d2 - 1)  # -1 表示不能射到右边那个机器人
            while right0 < m and walls[right0] <= right_x:
                right0 += 1
            f0 = max(left_res, f1 + right0 - cur1)  # 下标在 [cur1, right0-1] 中的墙都能摧毁

            # 往右射，右边那个机器人往右射，墙的坐标范围为 [x, right_x]
            right_x = min(x + d, x2 - 1)  # -1 表示不能射到右边那个机器人
            while right1 < m and walls[right1] <= right_x:
                right1 += 1
            f1 = max(left_res, f1 + right1 - cur1)  # 下标在 [cur1, right1-1] 中的墙都能摧毁
        return f1

###java

class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length, m = walls.length;
        int[][] a = new int[n + 2][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = robots[i];
            a[i][1] = distance[i];
        }
        a[n + 1][0] = Integer.MAX_VALUE;
        Arrays.sort(a, (p, q) -> p[0] - q[0]);
        Arrays.sort(walls);

        int f0 = 0, f1 = 0, left = 0, cur = 0, right0 = 0, right1 = 0;
        for (int i = 1; i <= n; i++) {
            int x = a[i][0], d = a[i][1];

            // 往左射，墙的坐标范围为 [leftX, x]
            int leftX = Math.max(x - d, a[i - 1][0] + 1); // +1 表示不能射到左边那个机器人
            while (left < m && walls[left] < leftX) {
                left++;
            }
            while (cur < m && walls[cur] < x) {
                cur++;
            }
            int cur1 = cur;
            if (cur < m && walls[cur] == x) {
                cur++;
            }
            int leftRes = f0 + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            // 往右射，右边那个机器人往左射，墙的坐标范围为 [x, rightX]
            int x2 = a[i + 1][0], d2 = a[i + 1][1];
            int rightX = Math.min(x + d, x2 - d2 - 1); // -1 表示不能射到右边那个机器人
            while (right0 < m && walls[right0] <= rightX) {
                right0++;
            }
            f0 = Math.max(leftRes, f1 + right0 - cur1); // 下标在 [cur1, right0-1] 中的墙都能摧毁

            // 往右射，右边那个机器人往右射，墙的坐标范围为 [x, rightX]
            rightX = Math.min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人
            while (right1 < m && walls[right1] <= rightX) {
                right1++;
            }
            f1 = Math.max(leftRes, f1 + right1 - cur1); // 下标在 [cur1, right1-1] 中的墙都能摧毁
        }
        return f1;
    }

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

###cpp

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size(), m = walls.size();
        struct Pair { int x, d; };
        vector<Pair> a(n + 2);
        for (int i = 0; i < n; i++) {
            a[i] = {robots[i], distance[i]};
        }
        a[n + 1].x = INT_MAX;
        ranges::sort(a, {}, &Pair::x);
        ranges::sort(walls);

        int f0 = 0, f1 = 0, left = 0, cur = 0, right0 = 0, right1 = 0;
        for (int i = 1; i <= n; i++) {
            auto [x, d] = a[i];

            // 往左射，墙的坐标范围为 [left_x, x]
            int left_x = max(x - d, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
            while (left < m && walls[left] < left_x) {
                left++;
            }
            while (cur < m && walls[cur] < x) {
                cur++;
            }
            int cur1 = cur;
            if (cur < m && walls[cur] == x) {
                cur++;
            }
            int left_res = f0 + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁

            // 往右射，右边那个机器人往左射，墙的坐标范围为 [x, right_x]
            auto [x2, d2] = a[i + 1];
            int right_x = min(x + d, x2 - d2 - 1); // -1 表示不能射到右边那个机器人
            while (right0 < m && walls[right0] <= right_x) {
                right0++;
            }
            f0 = max(left_res, f1 + right0 - cur1); // 下标在 [cur1, right0-1] 中的墙都能摧毁

            // 往右射，右边那个机器人往右射，墙的坐标范围为 [x, right_x]
            right_x = min(x + d, x2 - 1); // -1 表示不能射到右边那个机器人
            while (right1 < m && walls[right1] <= right_x) {
                right1++;
            }
            f1 = max(left_res, f1 + right1 - cur1); // 下标在 [cur1, right1-1] 中的墙都能摧毁
        }
        return f1;
    }
};

###go

func maxWalls(robots []int, distance []int, walls []int) int {
n, m := len(robots), len(walls)
type pair struct{ x, d int }
a := make([]pair, n+2)
for i, x := range robots {
a[i] = pair{x, distance[i]}
}
a[n+1].x = math.MaxInt // 哨兵
slices.SortFunc(a, func(a, b pair) int { return a.x - b.x })
slices.Sort(walls)

var f0, f1, left, cur, right0, right1 int
for i := 1; i <= n; i++ {
p := a[i]

// 往左射，墙的坐标范围为 [leftX, p.x]
leftX := max(p.x-p.d, a[i-1].x+1) // +1 表示不能射到左边那个机器人
for left < m && walls[left] < leftX {
left++
}
for cur < m && walls[cur] < p.x {
cur++
}
cur1 := cur
if cur < m && walls[cur] == p.x {
cur++
}
leftRes := f0 + cur - left // 下标在 [left, cur-1] 中的墙都能摧毁

// 往右射，右边那个机器人往左射，墙的坐标范围为 [p.x, rightX]
q := a[i+1]
rightX := min(p.x+p.d, q.x-q.d-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
for right0 < m && walls[right0] <= rightX {
right0++
}
f0 = max(leftRes, f1+right0-cur1) // 下标在 [cur1, right0-1] 中的墙都能摧毁

// 往右射，右边那个机器人往右射，墙的坐标范围为 [p.x, rightX]
rightX = min(p.x+p.d, q.x-1) // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
for right1 < m && walls[right1] <= rightX {
right1++
}
f1 = max(leftRes, f1+right1-cur1) // 下标在 [cur1, right0-1] 中的墙都能摧毁
}
return f1
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n + m\log m)$，其中 $n$ 是 $\textit{robots}$ 的长度，$m$ 是 $\textit{walls}$ 的长度。瓶颈在排序上。
空间复杂度：$\mathcal{O}(n)$。忽略排序的栈开销。

专题训练

见下面动态规划题单的「六、状态机 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
三种写法：记忆化搜索 / 递推 / 空间优化（Python/Java/C++/Go）endlesscheng
2025年1月12日 12:34

三种写法：记忆化搜索 / 递推 / 空间优化（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年1月12日 12:34

请先完成不允许感化的版本：64. 最小路径和，讲解。

本题相当于可以不选路径上的至多 $2$ 个数。

多一个约束，就多一个参数。

额外增加一个参数 $k$，定义 $\textit{dfs}(i,j,k)$ 表示从 $(0,0)$ 走到 $(i,j)$，在可用感化次数为 $k$ 的情况下，可以获得的最大金币数。

用「选或不选」分类讨论：

选：$\textit{dfs}(i,j,k) = \max(\textit{dfs}(i - 1, j, k), \textit{dfs}(i, j - 1, k)) + \textit{coins}[i][j]$。
不选（感化）：如果 $k>0$ 且 $\textit{coins}[i][j]<0$，则可以不选，$\textit{dfs}(i,j,k) = \max(\textit{dfs}(i - 1, j, k-1), \textit{dfs}(i, j - 1, k-1))$。

两种情况取最大值。

递归边界：

$\textit{dfs}(-1,j,k)=\textit{dfs}(i,-1,k)=-\infty$。用 $-\infty$ 表示不合法的状态，从而保证 $\max$ 不会取到不合法的状态。
$\textit{dfs}(0,0,0)=\textit{coins}[0][0]$。
$\textit{dfs}(0,0,k>0)=\max(\textit{coins}[0][0],0)$。

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

⚠注意：由于答案可能是负数，所以记忆化数组的初始值不能是 $-1$。可以初始化成 $-\infty$。

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

一、记忆化搜索

###py

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0 or j < 0:
                return -inf
            x = coins[i][j]
            if i == 0 and j == 0:
                return max(x, 0) if k else x
            res = max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x  # 选
            if k and x < 0:
                res = max(res, dfs(i - 1, j, k - 1), dfs(i, j - 1, k - 1))  # 不选
            return res

        ans = dfs(len(coins) - 1, len(coins[0]) - 1, 2)
        dfs.cache_clear()  # 避免超出内存限制
        return ans

###java

class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] memo = new int[m][n][3];
        for (int[][] mat : memo) {
            for (int[] row : mat) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }
        }
        return dfs(m - 1, n - 1, 2, coins, memo);
    }

    private int dfs(int i, int j, int k, int[][] coins, int[][][] memo) {
        if (i < 0 || j < 0) {
            return Integer.MIN_VALUE;
        }
        int x = coins[i][j];
        if (i == 0 && j == 0) {
            return k > 0 ? Math.max(x, 0) : x;
        }
        if (memo[i][j][k] != Integer.MIN_VALUE) { // 之前计算过
            return memo[i][j][k];
        }
        int res = Math.max(dfs(i - 1, j, k, coins, memo), dfs(i, j - 1, k, coins, memo)) + x; // 选
        if (k > 0 && x < 0) {
            res = Math.max(res, Math.max(dfs(i - 1, j, k - 1, coins, memo), dfs(i, j - 1, k - 1, coins, memo))); // 不选
        }
        return memo[i][j][k] = res; // 记忆化
    }
}

###cpp

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        vector memo(m, vector(n, array<int, 3>{INT_MIN, INT_MIN, INT_MIN}));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0 || j < 0) {
                return INT_MIN;
            }
            int x = coins[i][j];
            if (i == 0 && j == 0) {
                return memo[i][j][k] = k ? max(x, 0) : x;
            }
            int& res = memo[i][j][k]; // 注意这里是引用
            if (res != INT_MIN) { // 之前计算过
                return res;
            }
            res = max(dfs(i - 1, j, k), dfs(i, j - 1, k)) + x; // 选
            if (k && x < 0) {
                res = max({res, dfs(i - 1, j, k - 1), dfs(i, j - 1, k - 1)}); // 不选
            }
            return res;
        };
        return dfs(m - 1, n - 1, 2);
    }
};

###go

func maximumAmount(coins [][]int) int {
m, n := len(coins), len(coins[0])
memo := make([][][3]int, m)
for i := range memo {
memo[i] = make([][3]int, n)
for j := range memo[i] {
for k := range memo[i][j] {
memo[i][j][k] = math.MinInt
}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 {
return math.MinInt
}
x := coins[i][j]
if i == 0 && j == 0 {
if k == 0 {
return x
}
return max(x, 0)
}
p := &memo[i][j][k]
if *p != math.MinInt { // 之前计算过
return *p
}
res := max(dfs(i-1, j, k), dfs(i, j-1, k)) + x // 选
if x < 0 && k > 0 {
res = max(res, dfs(i-1, j, k-1), dfs(i, j-1, k-1)) // 不选
}
*p = res // 记忆化
return res
}
return dfs(m-1, n-1, 2)
}

复杂度分析

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

二、1:1 翻译成递推

1:1 地把记忆化搜索翻译成递推，见讲解。

代码实现时，可以把 $f[0][1][k]$ 初始化成 $0$，这样我们无需单独计算 $f[1][1]$。

###py

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        f = [[[-inf] * 3 for _ in range(n + 1)] for _ in range(m + 1)]
        f[0][1] = [0] * 3
        for i, row in enumerate(coins):
            for j, x in enumerate(row):
                f[i + 1][j + 1][0] = max(f[i + 1][j][0], f[i][j + 1][0]) + x
                f[i + 1][j + 1][1] = max(f[i + 1][j][1] + x, f[i][j + 1][1] + x,
                                         f[i + 1][j][0], f[i][j + 1][0])
                f[i + 1][j + 1][2] = max(f[i + 1][j][2] + x, f[i][j + 1][2] + x,
                                         f[i + 1][j][1], f[i][j + 1][1])
        return f[m][n][2]

###java

class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] f = new int[m + 1][n + 1][3];
        for (int[] row : f[0]) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        Arrays.fill(f[0][1], 0);
        for (int i = 0; i < m; i++) {
            Arrays.fill(f[i + 1][0], Integer.MIN_VALUE);
            for (int j = 0; j < n; j++) {
                int x = coins[i][j];
                f[i + 1][j + 1][0] = Math.max(f[i + 1][j][0], f[i][j + 1][0]) + x;
                f[i + 1][j + 1][1] = Math.max(
                        Math.max(f[i + 1][j][1], f[i][j + 1][1]) + x,
                        Math.max(f[i + 1][j][0], f[i][j + 1][0])
                );
                f[i + 1][j + 1][2] = Math.max(
                        Math.max(f[i + 1][j][2], f[i][j + 1][2]) + x,
                        Math.max(f[i + 1][j][1], f[i][j + 1][1])
                );
            }
        }
        return f[m][n][2];
    }
}

###cpp

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(), n = coins[0].size();
        vector f(m + 1, vector(n + 1, array<int, 3>{INT_MIN / 2, INT_MIN / 2, INT_MIN / 2}));
        f[0][1] = {0, 0, 0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = coins[i][j];
                f[i + 1][j + 1][0] = max(f[i + 1][j][0], f[i][j + 1][0]) + x;
                f[i + 1][j + 1][1] = max({f[i + 1][j][1] + x, f[i][j + 1][1] + x,
                                          f[i + 1][j][0], f[i][j + 1][0]});
                f[i + 1][j + 1][2] = max({f[i + 1][j][2] + x, f[i][j + 1][2] + x,
                                          f[i + 1][j][1], f[i][j + 1][1]});
            }
        }
        return f[m][n][2];
    }
};

###go

func maximumAmount(coins [][]int) int {
m, n := len(coins), len(coins[0])
f := make([][][3]int, m+1)
for i := range f {
f[i] = make([][3]int, n+1)
}
for j := range f[0] {
f[0][j] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}
}
f[0][1] = [3]int{}
for i, row := range coins {
f[i+1][0] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}
for j, x := range row {
f[i+1][j+1][0] = max(f[i+1][j][0], f[i][j+1][0]) + x
f[i+1][j+1][1] = max(f[i+1][j][1]+x, f[i][j+1][1]+x, f[i+1][j][0], f[i][j+1][0])
f[i+1][j+1][2] = max(f[i+1][j][2]+x, f[i][j+1][2]+x, f[i+1][j][1], f[i][j+1][1])
}
}
return f[m][n][2]
}

复杂度分析

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

三、空间优化

举个例子，在计算 $f[1][1]$ 时，会用到 $f[0][1]$，但是之后就不再用到了。那么干脆把 $f[1][1]$ 记到 $f[0][1]$ 中，这样对于 $f[1][2]$ 来说，它需要的数据就在 $f[0][1]$ 和 $f[0][2]$ 中。$f[1][2]$ 算完后也可以同样记到 $f[0][2]$ 中。

所以第一个维度可以去掉。

具体可以看【基础算法精讲 18】中的讲解。本题的转移方程类似完全背包，故整体采用正序遍历（但内部的 $k$ 要倒序）。

###py

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        n = len(coins[0])
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[1] = [0] * 3
        for row in coins:
            for j, x in enumerate(row):
                f[j + 1][2] = max(f[j][2] + x, f[j + 1][2] + x, f[j][1], f[j + 1][1])
                f[j + 1][1] = max(f[j][1] + x, f[j + 1][1] + x, f[j][0], f[j + 1][0])
                f[j + 1][0] = max(f[j][0], f[j + 1][0]) + x
        return f[n][2]

###py

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        max = lambda a, b: a if a > b else b
        n = len(coins[0])
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[1] = [0] * 3
        for row in coins:
            for j, x in enumerate(row):
                f[j + 1][2] = max(max(f[j][2], f[j + 1][2]) + x, max(f[j][1], f[j + 1][1]))
                f[j + 1][1] = max(max(f[j][1], f[j + 1][1]) + x, max(f[j][0], f[j + 1][0]))
                f[j + 1][0] = max(f[j][0], f[j + 1][0]) + x
        return f[n][2]

###java

class Solution {
    public int maximumAmount(int[][] coins) {
        int n = coins[0].length;
        int[][] f = new int[n + 1][3];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        Arrays.fill(f[1], 0);
        for (int[] row : coins) {
            for (int j = 0; j < n; j++) {
                int x = row[j];
                f[j + 1][2] = Math.max(
                        Math.max(f[j][2], f[j + 1][2]) + x,
                        Math.max(f[j][1], f[j + 1][1])
                );
                f[j + 1][1] = Math.max(
                        Math.max(f[j][1], f[j + 1][1]) + x,
                        Math.max(f[j][0], f[j + 1][0])
                );
                f[j + 1][0] = Math.max(f[j][0], f[j + 1][0]) + x;
            }
        }
        return f[n][2];
    }
}

###cpp

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int n = coins[0].size();
        vector f(n + 1, array<int, 3>{INT_MIN / 2, INT_MIN / 2, INT_MIN / 2});
        f[1] = {0, 0, 0};
        for (auto& row : coins) {
            for (int j = 0; j < n; j++) {
                int x = row[j];
                f[j + 1][2] = max({f[j][2] + x, f[j + 1][2] + x, f[j][1], f[j + 1][1]});
                f[j + 1][1] = max({f[j][1] + x, f[j + 1][1] + x, f[j][0], f[j + 1][0]});
                f[j + 1][0] = max(f[j][0], f[j + 1][0]) + x;
            }
        }
        return f[n][2];
    }
};

###go

func maximumAmount(coins [][]int) int {
n := len(coins[0])
f := make([][3]int, n+1)
for j := range f {
f[j] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}
}
f[1] = [3]int{}
for _, row := range coins {
for j, x := range row {
f[j+1][2] = max(f[j][2]+x, f[j+1][2]+x, f[j][1], f[j+1][1])
f[j+1][1] = max(f[j][1]+x, f[j+1][1]+x, f[j][0], f[j+1][0])
f[j+1][0] = max(f[j][0], f[j+1][0]) + x
}
}
return f[n][2]
}

复杂度分析

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

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

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
用栈维护机器人（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2023年6月25日 12:16

用栈维护机器人（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2023年6月25日 12:16

推荐先完成本题的简单版本：735. 行星碰撞，我的题解。

从左到右遍历这些机器人（需要先按照位置排序），向右的机器人会和向左的机器人碰撞。

遍历到一个向左的机器人时，我们需要找到左边最近的未移除的机器人。这可以用一个栈维护。

如果当前机器人向右，那么直接入栈，继续向后遍历。

如果当前机器人向左，设其健康度为 $h$，栈顶机器人的健康度为 $\textit{top}$，分类讨论：

如果 $\textit{top} > h$，那么移除当前机器人，$\textit{top}$ 减一。
如果 $\textit{top} = h$，那么两个机器人都移除。
如果 $\textit{top} < h$，那么移除栈顶机器人，$h$ 减一。
如此循环，直到当前机器人被移除，或者栈顶为空。

⚠注意：比大小的这两个健康度都是正整数，所以减一的那个健康度一定大于 $1$。所以减一后，健康度大于 $0$。

代码实现时，直接在 $\textit{healths}$ 上修改，移除机器人 $i$ 相当于把 $\textit{healths}[i]$ 置为 $0$。最后返回 $\textit{healths}$ 中的正数。

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        # 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
        idx = sorted(range(len(positions)), key=lambda i: positions[i])

        st = []
        for i in idx:
            if directions[i] == 'R':  # 机器人 i 向右
                st.append(i)
                continue
            while st:  # 栈顶机器人向右
                j = st[-1]
                if healths[j] > healths[i]:  # 栈顶机器人的健康度大
                    healths[i] = 0  # 移除机器人 i
                    healths[j] -= 1
                    break
                if healths[j] == healths[i]:  # 健康度一样大，都移除
                    healths[i] = 0
                    healths[j] = 0
                    st.pop()
                    break
                # 机器人 i 的健康度大
                healths[i] -= 1
                healths[j] = 0  # 移除机器人 j
                st.pop()

        # 返回幸存机器人的健康度
        return [h for h in healths if h > 0]

class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        // 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> positions[i] - positions[j]);

        int[] st = new int[n];
        int top = -1;
        for (int i : idx) {
            if (directions.charAt(i) == 'R') { // 机器人 i 向右
                st[++top] = i;
                continue;
            }
            while (top >= 0) { // 栈顶机器人向右
                int j = st[top];
                if (healths[j] > healths[i]) { // 栈顶机器人的健康度大
                    healths[i] = 0; // 移除机器人 i
                    healths[j]--;
                    break;
                }
                if (healths[j] == healths[i]) { // 健康度一样大，都移除
                    healths[i] = 0;
                    healths[j] = 0;
                    top--;
                    break;
                }
                // 机器人 i 的健康度大
                healths[i]--;
                healths[j] = 0; // 移除机器人 j
                top--;
            }
        }

        // 返回幸存机器人的健康度
        List<Integer> ans = new ArrayList<>();
        for (int h : healths) {
            if (h > 0) {
                ans.add(h);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
        int n = positions.size();
        // 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
        vector<int> idx(n);
        ranges::iota(idx, 0); // idx[i] = i
        ranges::sort(idx, {}, [&](int i) { return positions[i]; });

        stack<int> st;
        for (int i : idx) {
            if (directions[i] == 'R') { // 机器人 i 向右
                st.push(i);
                continue;
            }
            while (!st.empty()) { // 栈顶机器人向右
                int j = st.top();
                if (healths[j] > healths[i]) { // 栈顶机器人的健康度大
                    healths[i] = 0; // 移除机器人 i
                    healths[j]--;
                    break;
                }
                if (healths[j] == healths[i]) { // 健康度一样大，都移除
                    healths[i] = 0;
                    healths[j] = 0;
                    st.pop();
                    break;
                }
                // 机器人 i 的健康度大
                healths[i]--;
                healths[j] = 0; // 移除机器人 j
                st.pop();
            }
        }

        // 返回幸存机器人的健康度
        vector<int> ans;
        for (int h : healths) {
            if (h > 0) {
                ans.push_back(h);
            }
        }
        return ans;
    }
};

int* _positions;

int cmp(const void* i, const void* j) {
    return _positions[*(int*)i] - _positions[*(int*)j];
}

int* survivedRobotsHealths(int* positions, int positionsSize, int* healths, int healthsSize, char* directions, int* returnSize) {
    int n = positionsSize;
    // 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
    int* idx = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        idx[i] = i;
    }
    _positions = positions;
    qsort(idx, n, sizeof(int), cmp);

    int* st = malloc(n * sizeof(int));
    int top = -1;
    for (int k = 0; k < n; k++) {
        int i = idx[k];
        if (directions[i] == 'R') { // 机器人 i 向右
            st[++top] = i;
            continue;
        }
        while (top >= 0) { // 栈顶机器人向右
            int j = st[top];
            if (healths[j] > healths[i]) { // 栈顶机器人的健康度大
                healths[i] = 0; // 移除机器人 i
                healths[j]--;
                break;
            }
            if (healths[j] == healths[i]) { // 健康度一样大，都移除
                healths[i] = 0;
                healths[j] = 0;
                top--;
                break;
            }
            // 机器人 i 的健康度大
            healths[i]--;
            healths[j] = 0; // 移除机器人 j
            top--;
        }
    }

    free(idx);

    // 返回幸存机器人的健康度
    int* ans = st;
    *returnSize = 0;
    for (int i = 0; i < n; i++) {
        if (healths[i] > 0) {
            ans[(*returnSize)++] = healths[i];
        }
    }
    return ans;
}

func survivedRobotsHealths(positions []int, healths []int, directions string) (ans []int) {
// 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
idx := make([]int, len(positions))
for i := range idx {
idx[i] = i
}
slices.SortFunc(idx, func(i, j int) int { return positions[i] - positions[j] })

st := []int{}
for _, i := range idx {
if directions[i] == 'R' { // 机器人 i 向右
st = append(st, i)
continue
}
for len(st) > 0 { // 栈顶机器人向右
j := st[len(st)-1]
if healths[j] > healths[i] { // 栈顶机器人的健康度大
healths[i] = 0 // 移除机器人 i
healths[j]--
break
}
if healths[j] == healths[i] { // 健康度一样大，都移除
healths[i] = 0
healths[j] = 0
st = st[:len(st)-1]
break
}
// 机器人 i 的健康度大
healths[i]--
healths[j] = 0 // 移除机器人 j
st = st[:len(st)-1]
}
}

// 返回幸存机器人的健康度
for _, h := range healths {
if h > 0 {
ans = append(ans, h)
}
}
return
}

var survivedRobotsHealths = function(positions, healths, directions) {
    // 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
    const idx = Array.from({ length: positions.length }, (_, i) => i)
                     .sort((i, j) => positions[i] - positions[j]);

    const st = [];
    for (const i of idx) {
        if (directions[i] === 'R') { // 机器人 i 向右
            st.push(i);
            continue;
        }
        while (st.length > 0) { // 栈顶机器人向右
            const j = st[st.length - 1];
            if (healths[j] > healths[i]) { // 栈顶机器人的健康度大
                healths[i] = 0; // 移除机器人 i
                healths[j] -= 1;
                break;
            }
            if (healths[j] === healths[i]) { // 健康度一样大，都移除
                healths[i] = 0;
                healths[j] = 0;
                st.pop();
                break;
            }
            // 机器人 i 的健康度大
            healths[i] -= 1;
            healths[j] = 0; // 移除机器人 j
            st.pop();
        }
    }

    // 返回幸存机器人的健康度
    return healths.filter(h => h > 0);
};

impl Solution {
    pub fn survived_robots_healths(positions: Vec<i32>, mut healths: Vec<i32>, directions: String) -> Vec<i32> {
        // 创建一个下标数组，对下标数组排序，这样不会打乱输入顺序
        let mut idx = (0..positions.len()).collect::<Vec<_>>();
        idx.sort_unstable_by_key(|&i| positions[i]);

        let directions = directions.as_bytes();
        let mut st = vec![];

        for i in idx {
            if directions[i] == b'R' { // 机器人 i 向右
                st.push(i);
                continue;
            }
            while let Some(&j) = st.last() { // 栈顶机器人向右
                if healths[j] > healths[i] { // 栈顶机器人的健康度大
                    healths[i] = 0; // 移除机器人 i
                    healths[j] -= 1;
                    break;
                }
                if healths[j] == healths[i] { // 健康度一样大，都移除
                    healths[i] = 0;
                    healths[j] = 0;
                    st.pop();
                    break;
                }
                // 机器人 i 的健康度大
                healths[i] -= 1;
                healths[j] = 0; // 移除机器人 j
                st.pop();
            }
        }

        // 返回幸存机器人的健康度
        healths.into_iter().filter(|&h| h > 0).collect()
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{positions}$ 的长度。瓶颈在排序上。虽然我们写了个二重循环，但每个元素至多入栈出栈各一次，所以二重循环的总循环次数是 $\mathcal{O}(n)$ 的。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面数据结构题单的「§3.3 邻项消除」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两种方法：贪心 + 暴力匹配 / Z 函数（Python/Java/C++/Go）endlesscheng
2025年3月2日 21:45

两种方法：贪心 + 暴力匹配 / Z 函数（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年3月2日 21:45

方法一：暴力修改

首先说做法。下文把 $\textit{str}_1$ 简记为 $s$，把 $\textit{str}_2$ 简记为 $t$。

先模拟：处理 $s$ 中的 T，把字符串 $t$ 填入答案的对应位置，如果发现矛盾，就返回空串。没填的位置（待定位置）初始化为 $\texttt{a}$。

再贪心：从左到右检查 F 对应的答案子串，如果发现子串和 $t$ 相同，那么把子串的最后一个待定位置改成 $\texttt{b}$。

本题的贪心策略是简单的，难点在正确性上。考虑如下问题：

按照上述贪心策略，是否存在一种情况，当我们把待定位置改成 $\texttt{b}$ 后，前面的某个 F 对应子串反而变成和 $t$ 相同了？

情况一

$t$ 全为 $\texttt{a}$ 的情况。

这是容易证明的，因为把待定位置改成 $\texttt{b}$ 后，前面的受到影响的子串（包含这个 $\texttt{b}$ 的子串）一定不会等于 $t$，毕竟 $t$ 只有 $\texttt{a}$。

例如 $t=\texttt{aaa}$，现在 $\textit{ans}=\texttt{aaa?????aaa}$。其中 $\texttt{?}$ 表示待定位置，初始值为 $\texttt{a}$。

我们遇到的第一个待定位置就会改成 $\texttt{b}$，后续所有包含这个 $\texttt{b}$ 的子串必然不等于 $t$，所以仍然为默认值 $\texttt{a}$。
直到我们遇到下一个需要改成 $\texttt{b}$ 的待定位置。
最终 $\textit{ans} = \texttt{aaa}\underline{\texttt{baabb}}\texttt{aaa}$。请动手算算，特别注意最后一个 $\texttt{b}$ 是怎么改的。

情况二

下面讨论 $t$ 包含不等于 $\texttt{a}$ 的字母的情况。

猜想：$t$ 形如 $t' + \texttt{aa\ldots a} + t'$。例如 $\texttt{baab},\texttt{baaaaba},\texttt{abaaaba}$ 等。

例如 $t=\texttt{baaaaba}$，即 $\texttt{ba} + \texttt{aaa} + \texttt{ba}$。

设 $\textit{ans} = \texttt{baaaaba???baaaaba}$。中间的 $\texttt{???}$ 不能全为 $\texttt{a}$，改成 $\texttt{aab}$，得 $\texttt{baaaaba}\underline{\texttt{aab}}\texttt{baaaaba}$，这里产生的 $\texttt{baaab}$ 可以保证前面的 F 对应子串不会和 $t$ 相同。

这可以推广到一般情况。抛砖引玉，欢迎在评论区发表你的证明。

同理，一旦我们修改了 $\textit{ans}[j]$，那么后面包含 $\textit{ans}[j]$ 的子串都不会和 $t$ 相同。所以只需改最后一个待定位置，不会出现改子串倒数第二个待定位置的情况。进一步地，可以直接跳到 $j+1$ 继续循环，这个优化用在方法二中。

###py

class Solution:
    def generateString(self, s: str, t: str) -> str:
        n, m = len(s), len(t)
        ans = ['?'] * (n + m - 1)  # ? 表示待定位置

        # 处理 T
        for i, b in enumerate(s):
            if b != 'T':
                continue
            # 子串必须等于 t
            for j, c in enumerate(t):
                v = ans[i + j]
                if v != '?' and v != c:
                    return ""
                ans[i + j] = c

        old_ans = ans
        ans = ['a' if c == '?' else c for c in ans]  # 待定位置的初始值为 a

        # 处理 F
        for i, b in enumerate(s):
            if b != 'F':
                continue
            # 子串必须不等于 t
            if ''.join(ans[i: i + m]) != t:
                continue
            # 找最后一个待定位置
            for j in range(i + m - 1, i - 1, -1):
                if old_ans[j] == '?':  # 之前填 a，现在改成 b
                    ans[j] = 'b'
                    break
            else:
                return ""

        return ''.join(ans)

###java

class Solution {
    public String generateString(String S, String t) {
        char[] s = S.toCharArray();
        int n = s.length;
        int m = t.length();
        char[] ans = new char[n + m - 1];
        Arrays.fill(ans, '?'); // '?' 表示待定位置

        // 处理 T
        for (int i = 0; i < n; i++) {
            if (s[i] != 'T') {
                continue;
            }
            // 子串必须等于 t
            for (int j = 0; j < m; j++) {
                char v = ans[i + j];
                if (v != '?' && v != t.charAt(j)) {
                    return "";
                }
                ans[i + j] = t.charAt(j);
            }
        }

        char[] oldAns = ans.clone();
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == '?') {
                ans[i] = 'a'; // 待定位置的初始值为 'a'
            }
        }

        // 处理 F
        for (int i = 0; i < n; i++) {
            if (s[i] != 'F') {
                continue;
            }
            // 子串必须不等于 t
            if (!new String(ans, i, m).equals(t)) {
                continue;
            }
            // 找最后一个待定位置
            boolean ok = false;
            for (int j = i + m - 1; j >= i; j--) {
                if (oldAns[j] == '?') { // 之前填 'a'，现在改成 'b'
                    ans[j] = 'b';
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return "";
            }
        }

        return new String(ans);
    }
}

###cpp

class Solution {
public:
    string generateString(string s, string t) {
        int n = s.size(), m = t.size();
        string ans(n + m - 1, '?'); // ? 表示待定位置

        // 处理 T
        for (int i = 0; i < n; i++) {
            if (s[i] != 'T') {
                continue;
            }
            // 子串必须等于 t
            for (int j = 0; j < m; j++) {
                char v = ans[i + j];
                if (v != '?' && v != t[j]) {
                    return "";
                }
                ans[i + j] = t[j];
            }
        }

        string old_ans = ans;
        for (char& c : ans) {
            if (c == '?') {
                c = 'a'; // 待定位置的初始值为 a
            }
        }

        // 处理 F
        for (int i = 0; i < n; i++) {
            if (s[i] != 'F') {
                continue;
            }
            // 子串必须不等于 t
            if (string(ans.begin() + i, ans.begin() + i + m) != t) {
                continue;
            }
            // 找最后一个待定位置
            bool ok = false;
            for (int j = i + m - 1; j >= i; j--) {
                if (old_ans[j] == '?') { // 之前填 a，现在改成 b
                    ans[j] = 'b';
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return "";
            }
        }

        return ans;
    }
};

###go

func generateString(s, T string) string {
    n, m := len(s), len(T)
    t := []byte(T)
    ans := bytes.Repeat([]byte{'?'}, n+m-1) // ? 表示待定位置
    
    // 处理 T
    for i, b := range s {
        if b != 'T' {
            continue
        }
        // sub 必须等于 t
        sub := ans[i : i+m]
        for j, c := range sub {
            if c != '?' && c != t[j] {
                return ""
            }
            sub[j] = t[j]
        }
    }
    oldAns := ans
    ans = bytes.ReplaceAll(ans, []byte{'?'}, []byte{'a'}) // 待定位置的初始值为 a

    // 处理 F
next:
    for i, b := range s {
        if b != 'F' {
            continue
        }
        // sub 必须不等于 t 
        sub := ans[i : i+m]
        if !bytes.Equal(sub, t) {
            continue
        }
        // 找最后一个待定位置
        old := oldAns[i : i+m]
        for j := m - 1; j >= 0; j-- {
            if old[j] == '?' { // 之前填 a，现在改成 b
                sub[j] = 'b'
                continue next
            }
        }
        return ""
    }

    return string(ans)
}

复杂度分析

时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $s$ 的长度，$m$ 是 $t$ 的长度。
空间复杂度：$\mathcal{O}(n+m)$。如果不考虑切片和返回值的话是 $\mathcal{O}(1)$。

方法二：Z 函数

在模拟（处理 $s$ 中的 T）的过程中，如果两个 $t$ 重叠，我们需要判断 $t$ 的某个长度的前后缀是否相同，这可以用 Z 函数直接解决。

判断 $\textit{ans}$ 子串是否等于 $t$ 也可以用 Z 函数。计算 $t + \textit{ans}$ 的 Z 函数，如果 $z[i+m]<m$，就说明从 $i$ 开始的 $\textit{ans}$ 子串不等于 $t$。

如果子串等于 $t$，那么找一个小于 $i+m$ 的最近待定位置，改成 $\texttt{b}$。这可以用一个数组 $\textit{preQ}$ 预处理每个 $\le i$ 的最近待定位置。

###py

class Solution:
    def calc_z(self, s: str) -> List[int]:
        n = len(s)
        z = [0] * n
        box_l, box_r = 0, 0  # z-box 左右边界（闭区间）
        for i in range(1, n):
            if i <= box_r:
                z[i] = min(z[i - box_l], box_r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                box_l, box_r = i, i + z[i]
                z[i] += 1
        z[0] = n
        return z

    def generateString(self, s: str, t: str) -> str:
        n, m = len(s), len(t)
        ans = ['?'] * (n + m - 1)

        # 处理 T
        z = self.calc_z(t)
        pre = -m
        for i, b in enumerate(s):
            if b != 'T':
                continue
            size = max(pre + m - i, 0)
            # t 的长为 size 的前后缀必须相同
            if size > 0 and z[m - size] < size:
                return ""
            # size 后的内容都是 '?'，填入 t
            ans[i + size: i + m] = t[size:]
            pre = i

        # 计算 <= i 的最近待定位置
        pre_q = [-1] * len(ans)
        pre = -1
        for i, c in enumerate(ans):
            if c == '?':
                ans[i] = 'a'  # 待定位置的初始值为 a
                pre = i
            pre_q[i] = pre

        # 找 ans 中的等于 t 的位置，可以用 KMP 或者 Z 函数
        z = self.calc_z(t + ''.join(ans))

        # 处理 F
        i = 0
        while i < n:
            if s[i] != 'F':
                i += 1
                continue
            # 子串必须不等于 t
            if z[m + i] < m:
                i += 1
                continue
            # 找最后一个待定位置
            j = pre_q[i + m - 1]
            if j < i:  # 没有
                return ""
            ans[j] = 'b'
            i = j + 1  # 直接跳过 j

        return ''.join(ans)

###java

class Solution {
    public String generateString(String S, String t) {
        char[] s = S.toCharArray();
        int n = s.length;
        int m = t.length();
        char[] ans = new char[n + m - 1];
        Arrays.fill(ans, '?');

        // 处理 T
        int[] z = calcZ(t);
        int pre = -m;
        for (int i = 0; i < n; i++) {
            if (s[i] != 'T') {
                continue;
            }
            int size = Math.max(pre + m - i, 0);
            // t 的长为 size 的前后缀必须相同
            if (size > 0 && z[m - size] < size) {
                return "";
            }
            // size 后的内容都是 '?'，填入 t
            for (int j = size; j < m; j++) {
                ans[i + j] = t.charAt(j);
            }
            pre = i;
        }

        // 计算 <= i 的最近待定位置
        int[] preQ = new int[ans.length];
        pre = -1;
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == '?') {
                ans[i] = 'a'; // 待定位置的初始值为 a
                pre = i;
            }
            preQ[i] = pre;
        }

        // 找 ans 中的等于 t 的位置，可以用 KMP 或者 Z 函数
        z = calcZ(t + new String(ans));

        // 处理 F
        for (int i = 0; i < n; i++) {
            if (s[i] != 'F') {
                continue;
            }
            // 子串必须不等于 t
            if (z[m + i] < m) {
                continue;
            }
            // 找最后一个待定位置
            int j = preQ[i + m - 1];
            if (j < i) { // 没有
                return "";
            }
            ans[j] = 'b';
            i = j; // 直接跳到 j
        }

        return new String(ans);
    }

    private int[] calcZ(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] z = new int[n];
        int boxL = 0; // z-box 左右边界（闭区间）
        int boxR = 0;
        for (int i = 1; i < n; i++) {
            if (i <= boxR) {
                z[i] = Math.min(z[i - boxL], boxR - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                boxL = i;
                boxR = i + z[i];
                z[i]++;
            }
        }
        z[0] = n;
        return z;
    }
}

###cpp

class Solution {
    vector<int> calc_z(const string& s) {
        int n = s.size();
        vector<int> z(n);
        int box_l = 0, box_r = 0; // z-box 左右边界（闭区间）
        for (int i = 1; i < n; i++) {
            if (i <= box_r) {
                z[i] = min(z[i - box_l], box_r - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                box_l = i;
                box_r = i + z[i];
                z[i]++;
            }
        }
        z[0] = n;
        return z;
    }

public:
    string generateString(string s, string t) {
        int n = s.size(), m = t.size();
        string ans(n + m - 1, '?');

        // 处理 T
        vector<int> z = calc_z(t);
        int pre = -m;
        for (int i = 0; i < n; i++) {
            if (s[i] != 'T') {
                continue;
            }
            int size = max(pre + m - i, 0);
            // t 的长为 size 的前后缀必须相同
            if (size > 0 && z[m - size] < size) {
                return "";
            }
            // size 后的内容都是 '?'，填入 t
            for (int j = size; j < m; j++) {
                ans[i + j] = t[j];
            }
            pre = i;
        }

        // 计算 <= i 的最近待定位置
        vector<int> pre_q(ans.size());
        pre = -1;
        for (int i = 0; i < ans.size(); i++) {
            if (ans[i] == '?') {
                ans[i] = 'a'; // 待定位置的初始值为 a
                pre = i;
            }
            pre_q[i] = pre;
        }

        // 找 ans 中的等于 t 的位置，可以用 KMP 或者 Z 函数
        z = calc_z(t + ans);

        // 处理 F
        for (int i = 0; i < n; i++) {
            if (s[i] != 'F') {
                continue;
            }
            // 子串必须不等于 t
            if (z[m + i] < m) {
                continue;
            }
            // 找最后一个待定位置
            int j = pre_q[i + m - 1];
            if (j < i) { // 没有
                return "";
            }
            ans[j] = 'b';
            i = j; // 直接跳到 j
        }

        return ans;
    }
};

###go

func calcZ(s string) []int {
    n := len(s)
    z := make([]int, n)
    boxL, boxR := 0, 0 // z-box 左右边界（闭区间）
    for i := 1; i < n; i++ {
        if i <= boxR {
            z[i] = min(z[i-boxL], boxR-i+1)
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            boxL, boxR = i, i+z[i]
            z[i]++
        }
    }
    z[0] = n
    return z
}

func generateString(s, t string) string {
    n, m := len(s), len(t)
    ans := bytes.Repeat([]byte{'?'}, n+m-1)

    // 处理 T
    pre := -m
    z := calcZ(t)
    for i, b := range s {
        if b != 'T' {
            continue
        }
        size := max(pre+m-i, 0)
        // t 的长为 size 的前后缀必须相同
        if size > 0 && z[m-size] < size {
            return ""
        }
        // size 后的内容都是 '?'，填入 t
        copy(ans[i+size:], t[size:])
        pre = i
    }

    // 计算 <= i 的最近待定位置
    preQ := make([]int, len(ans))
    pre = -1
    for i, c := range ans {
        if c == '?' {
            ans[i] = 'a' // 待定位置的初始值为 a
            pre = i
        }
        preQ[i] = pre
    }

    // 找 ans 中的等于 t 的位置，可以用 KMP 或者 Z 函数
    z = calcZ(t + string(ans))

    // 处理 F
    for i := 0; i < n; i++ {
        if s[i] != 'F' {
            continue
        }
        // 子串必须不等于 t 
        if z[m+i] < m {
            continue
        }
        // 找最后一个待定位置
        j := preQ[i+m-1]
        if j < i { // 没有
            return ""
        }
        ans[j] = 'b'
        i = j // 直接跳到 j
    }

    return string(ans)
}

复杂度分析

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

更多相似题目，见下面贪心题单中的「§3.1 字典序最小/最大」和字符串题单中的「二、Z 函数」。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
看下标为偶数/奇数的字符个数是否都一样（Python/Java/C++/Go）endlesscheng
2023年9月3日 20:15

看下标为偶数/奇数的字符个数是否都一样（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2023年9月3日 20:15

有一个更强的结论：改成 $j-i=2$，也是一样的。

既然可以交换相距为 $2$ 的字符，那么相距为 $4$ 的字符可以通过多次交换实现。例如 $x-y-z$ 变成 $y-x-z$ 变成 $y-z-x$ 变成 $z-y-x$。

依此类推，所有相距为偶数的字符都可以随意交换。

所以只需要看下标为偶数的字符个数是否都一样，以及下标为奇数的字符个数是否都一样。

视频讲解

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        return Counter(s1[::2]) == Counter(s2[::2]) and \
               Counter(s1[1::2]) == Counter(s2[1::2])

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int[][] cnt1 = new int[2][26];
        int[][] cnt2 = new int[2][26];
        for (int i = 0; i < s1.length(); i++) {
            cnt1[i % 2][s1.charAt(i) - 'a']++;
            cnt2[i % 2][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(cnt1, cnt2);
    }
}

class Solution {
public:
    bool checkStrings(string s1, string s2) {
        int cnt1[2][26]{}, cnt2[2][26]{};
        for (int i = 0; i < s1.length(); i++) {
            cnt1[i % 2][s1[i] - 'a']++;
            cnt2[i % 2][s2[i] - 'a']++;
        }
        return memcmp(cnt1, cnt2, sizeof(cnt1)) == 0;
    }
};

func checkStrings(s1, s2 string) bool {
var cnt1, cnt2 [2][26]int
for i, c := range s1 {
cnt1[i%2][c-'a']++
cnt2[i%2][s2[i]-'a']++
}
return cnt1 == cnt2
}

复杂度分析

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

思考题

改成 $j-i=3$ 要怎么做？

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
简单题，简单做（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2023年11月26日 12:20

简单题，简单做（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2023年11月26日 12:20

实际上，只需把每行右移 $k$ 次。无需判断奇偶，无需考虑左移。

为什么？如果一行左移 $k$ 次等于自己，那么这个过程的逆过程，就是把自己右移 $k$ 次，得到自己。

判断 $\textit{row}$ 右移 $k$ 次是否等于 $\textit{row}$，可以比较 $\textit{row}[j]$ 与右移 $k$ 次后的位置 $\textit{row}[(j+k)\bmod n]$ 是否相等。

###py

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        k %= len(mat[0])  # 右移 n 次等价于右移 0 次，右移 n+1 次等价于右移 1 次，依此类推，先模个 n
        return k == 0 or all(row == row[k:] + row[:k] for row in mat)

###py

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        n = len(mat[0])
        for row in mat:
            for j in range(n):
                if row[j] != row[(j + k) % n]:
                    return False
        return True

###java

class Solution {
    public boolean areSimilar(int[][] mat, int k) {
        int n = mat[0].length;
        for (int[] row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] != row[(j + k) % n]) {
                    return false;
                }
            }
        }
        return true;
    }
}

###cpp

class Solution {
public:
    bool areSimilar(vector<vector<int>>& mat, int k) {
        int n = mat[0].size();
        for (auto& row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] != row[(j + k) % n]) {
                    return false;
                }
            }
        }
        return true;
    }
};

###c

bool areSimilar(int** mat, int matSize, int* matColSize, int k) {
    int n = matColSize[0];
    for (int i = 0; i < matSize; i++) {
        int* row = mat[i];
        for (int j = 0; j < n; j++) {
            if (row[j] != row[(j + k) % n]) {
                return false;
            }
        }
    }
    return true;
}

###go

func areSimilar(mat [][]int, k int) bool {
n := len(mat[0])
for _, row := range mat {
for j, x := range row {
if x != row[(j+k)%n] {
return false
}
}
}
return true
}

###go

func areSimilar(mat [][]int, k int) bool {
k %= len(mat[0]) // 右移 n 次等价于右移 0 次，右移 n+1 次等价于右移 1 次，依此类推，先模个 n
for _, row := range mat {
if !slices.Equal(row, append(row[k:], row[:k]...)) {
return false
}
}
return true
}

###js

var areSimilar = function(mat, k) {
    const n = mat[0].length;
    for (const row of mat) {
        for (let j = 0; j < n; j++) {
            if (row[j] !== row[(j + k) % n]) {
                return false;
            }
        }
    }
    return true;
};

###rust

impl Solution {
    pub fn are_similar(mat: Vec<Vec<i32>>, k: i32) -> bool {
        let n = mat[0].len();
        let k = k as usize;
        for row in mat {
            for j in 0..n {
                if row[j] != row[(j + k) % n] {
                    return false;
                }
            }
        }
        true
    }
}

复杂度分析

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

详细解释

可能有同学脑筋没转过来，这里详细解释下。

如果给你两个数组 $a$ 和 $b$，要判断 $a$ 左移/右移后是否等于 $b$，那么 $a$ 左移 $k$ 次和右移 $k$ 次是不一样的。

但本题这两个数组都是 $a$，要判断 $a$ 左移/右移后是否等于 $a$ 自己。

由于 $a$ 左移 $k$ 次后和 $b$ 比较，等价于 $b$ 右移 $k$ 次后和 $a$ 比较。在 $b$ 就是 $a$ 的情况下，等价于 $a$ 自己右移 $k$ 次和 $a$ 比较。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
式子变形 + 分类讨论 + 复用代码（Python/Java/C++/Go）endlesscheng
2025年5月11日 12:18

式子变形 + 分类讨论 + 复用代码（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年5月11日 12:18

分析

设整个 $\textit{grid}$ 的元素和为 $\textit{total}$。

设第一部分的元素和为 $s$，那么第二部分的元素和为 $\textit{total}-s$。

不删元素：$s = \textit{total}-s$，即 $2s-\textit{total} = 0$。
删第一部分中的元素 $x$：$s - x = \textit{total}-s$，即 $2s-\textit{total} = x$。

据此，我们可以一边遍历 $\textit{grid}$，一边计算第一部分的元素和 $s$，一边用哈希集合记录遍历过的元素。

每一行/列遍历结束后，判断 $x=2s-\textit{total}$ 是否在哈希集合中，如果在，就说明存在 $x$，使得 $s - x = \textit{total}-s$ 成立。

小技巧：预先把 $0$ 加到哈希集合中，这样可以把不删和删合并成一种情况。

对于删第二部分中的元素的情况，可以把 $\textit{grid}$ 上下翻转，复用删第一部分中的元素的代码。

分类讨论

先计算水平分割的情况。

分类讨论：

对于只有一列（$n=1$）的情况，只能删除第一个数或者分割线上那个数。
对于只有一行（分割线在第一行与第二行之间）的情况，只能删除第一个数或者最后一个数。删除中间的数会导致第一部分不连通。
其余情况，可以随便删。

对于垂直分割，可以把 $\textit{grid}$ 旋转 $90$ 度，复用上述代码。

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

###py

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        total = sum(sum(row) for row in grid)

        # 能否水平分割
        def check(a: List[List[int]]) -> bool:
            m, n = len(a), len(a[0])

            # 删除上半部分中的一个数，能否满足要求
            def f(a: List[List[int]]) -> bool:
                st = {0}  # 0 对应不删除数字
                s = 0
                for i, row in enumerate(a[:-1]):
                    for j, x in enumerate(row):
                        s += x
                        # 第一行，不能删除中间元素
                        if i > 0 or j == 0 or j == n - 1:
                            st.add(x)
                    # 特殊处理只有一列的情况，此时只能删除第一个数或者分割线上那个数
                    if n == 1:
                        if s * 2 == total or s * 2 - total == a[0][0] or s * 2 - total == row[0]:
                            return True
                        continue
                    if s * 2 - total in st:
                        return True
                    # 如果分割到更下面，那么可以删第一行的元素
                    if i == 0:
                        st.update(row)
                return False

            # 删除上半部分中的数 or 删除下半部分中的数
            return f(a) or f(a[::-1])

        # 水平分割 or 垂直分割
        return check(grid) or check(list(zip(*grid)))

###java

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long total = 0;
        for (int[] row : grid) {
            for (int x : row) {
                total += x;
            }
        }
        
        // 水平分割 or 垂直分割
        return check(grid, total) || check(rotate(grid), total);
    }

    private boolean check(int[][] a, long total) {
        // 删除上半部分中的一个数
        if (f(a, total)) {
            return true;
        }
        reverse(a);
        // 删除下半部分中的一个数
        return f(a, total);
    }

    private boolean f(int[][] a, long total) {
        int m = a.length, n = a[0].length;
        Set<Long> st = new HashSet<>();
        st.add(0L); // 0 对应不删除数字
        long s = 0;
        for (int i = 0; i < m - 1; i++) {
            int[] row = a[i];
            for (int j = 0; j < n; j++) {
                int x = row[j];
                s += x;
                // 第一行，不能删除中间元素
                if (i > 0 || j == 0 || j == n - 1) {
                    st.add((long) x);
                }
            }
            // 特殊处理只有一列的情况，此时只能删除第一个数或者分割线上那个数
            if (n == 1) {
                if (s * 2 == total || s * 2 - total == a[0][0] || s * 2 - total == row[0]) {
                    return true;
                }
                continue;
            }
            if (st.contains(s * 2 - total)) {
                return true;
            }
            // 如果分割到更下面，那么可以删第一行的元素
            if (i == 0) {
                for (int x : row) {
                    st.add((long) x);
                }
            }
        }
        return false;
    }

    // 顺时针旋转矩阵 90°
    private int[][] rotate(int[][] a) {
        int m = a.length, n = a[0].length;
        int[][] b = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j];
            }
        }
        return b;
    }

    private void reverse(int[][] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int[] tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
}

###cpp

class Solution {
    // 顺时针旋转矩阵 90°
    vector<vector<int>> rotate(vector<vector<int>>& a) {
        int m = a.size(), n = a[0].size();
        vector b(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j];
            }
        }
        return b;
    }

public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long total = 0;
        for (auto& row : grid) {
            for (int x : row) {
                total += x;
            }
        }

        auto check = [&](vector<vector<int>> a) -> bool {
            int m = a.size(), n = a[0].size();

            auto f = [&]() -> bool {
                unordered_set<long long> st = {0}; // 0 对应不删除数字
                long long s = 0;
                for (int i = 0; i < m - 1; i++) {
                    auto& row = a[i];
                    for (int j = 0; j < n; j++) {
                        int x = row[j];
                        s += x;
                        // 第一行，不能删除中间元素
                        if (i > 0 || j == 0 || j == n - 1) {
                            st.insert(x);
                        }
                    }
                    // 特殊处理只有一列的情况，此时只能删除第一个数或者分割线上那个数
                    if (n == 1) {
                        if (s * 2 == total || s * 2 - total == a[0][0] || s * 2 - total == row[0]) {
                            return true;
                        }
                        continue;
                    }
                    if (st.contains(s * 2 - total)) {
                        return true;
                    }
                    // 如果分割到更下面，那么可以删第一行的元素
                    if (i == 0) {
                        for (int x : row) {
                            st.insert(x);
                        }
                    }
                }
                return false;
            };

            // 删除上半部分中的一个数
            if (f()) {
                return true;
            }
            ranges::reverse(a);
            // 删除下半部分中的一个数
            return f();
        };

        // 水平分割 or 垂直分割
        return check(grid) || check(rotate(grid));
    }
};

###go

func canPartitionGrid(grid [][]int) bool {
total := 0
for _, row := range grid {
for _, x := range row {
total += x
}
}

// 能否水平分割
check := func(a [][]int) bool {
m, n := len(a), len(a[0])
f := func() bool {
has := map[int]bool{0: true} // 0 对应不删除数字
s := 0
for i, row := range a[:m-1] {
for j, x := range row {
s += x
// 第一行，不能删除中间元素
if i > 0 || j == 0 || j == n-1 {
has[x] = true
}
}
// 特殊处理只有一列的情况，此时只能删除第一个数或者分割线上那个数
if n == 1 {
if s*2 == total || s*2-total == a[0][0] || s*2-total == row[0] {
return true
}
continue
}
if has[s*2-total] {
return true
}
// 如果分割到更下面，那么可以删第一行的元素
if i == 0 {
for _, x := range row {
has[x] = true
}
}
}
return false
}
// 删除上半部分中的一个数
if f() {
return true
}
slices.Reverse(a)
// 删除下半部分中的一个数
return f()
}

// 水平分割 or 垂直分割
return check(grid) || check(rotate(grid))
}

// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
m, n := len(a), len(a[0])
b := make([][]int, n)
for i := range b {
b[i] = make([]int, m)
}
for i, row := range a {
for j, x := range row {
b[j][m-1-i] = x
}
}
return b
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
前后缀分解（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2023年10月15日 12:12

前后缀分解（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2023年10月15日 12:12

请先完成本题的一维版本：238. 除了自身以外数组的乘积。

把矩阵平铺成一维数组，就是 238 题了。我们需要算出每个数左边所有数的乘积，以及右边所有数的乘积。

先算出从 $\textit{grid}[i][j]$ 的下一个元素开始，到最后一个元素 $\textit{grid}[n-1][m-1]$ 的乘积，记作 $\textit{suf}[i][j]$。这可以从最后一个数 $\textit{grid}[n-1][m-1]$ 开始，倒着遍历 $\textit{grid}$ 得到。

然后算出从第一个数 $\textit{grid}[0][0]$ 开始，到 $\textit{grid}[i][j]$ 的上一个元素的乘积，记作 $\textit{pre}[i][j]$。这可以从第一行第一列开始，正着遍历得到。

那么

$$
p[i][j] = \textit{pre}[i][j]\cdot \textit{suf}[i][j]
$$

代码实现时，可以先初始化 $p[i][j]=\textit{suf}[i][j]$，然后在计算 $\textit{pre}[i][j]$ 的过程中，把 $\textit{pre}[i][j]$ 乘到 $\textit{p}[i][j]$ 中，就得到了最终答案。这样写的话，$\textit{pre}$ 和 $\textit{suf}$ 可以直接用单个变量表示，无需创建数组。

代码实现时，注意取模。为什么可以在中途取模？原理见模运算的世界：当加减乘除遇上取模。

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        n, m = len(grid), len(grid[0])
        p = [[0] * m for _ in range(n)]

        suf = 1  # 后缀乘积
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                p[i][j] = suf  # p[i][j] 先初始化成后缀乘积
                suf = suf * grid[i][j] % MOD

        pre = 1  # 前缀乘积
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                p[i][j] = p[i][j] * pre % MOD  # 乘上前缀乘积
                pre = pre * x % MOD

        return p

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        final int MOD = 12345;
        int n = grid.length;
        int m = grid[0].length;
        int[][] p = new int[n][m];

        long suf = 1; // 后缀乘积
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                p[i][j] = (int) suf; // p[i][j] 先初始化成后缀乘积
                suf = suf * grid[i][j] % MOD;
            }
        }

        long pre = 1; // 前缀乘积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = (int) (p[i][j] * pre % MOD); // 乘上前缀乘积
                pre = pre * grid[i][j] % MOD;
            }
        }

        return p;
    }
}

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        constexpr int MOD = 12345;
        int n = grid.size(), m = grid[0].size();
        vector p(n, vector<int>(m));

        long long suf = 1; // 后缀乘积
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                p[i][j] = suf; // p[i][j] 先初始化成后缀乘积
                suf = suf * grid[i][j] % MOD;
            }
        }

        long long pre = 1; // 前缀乘积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = p[i][j] * pre % MOD; // 乘上前缀乘积
                pre = pre * grid[i][j] % MOD;
            }
        }

        return p;
    }
};

int** constructProductMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    const int MOD = 12345;
    int n = gridSize, m = gridColSize[0];
    int** p = malloc(n * sizeof(int*));
    *returnSize = n;
    *returnColumnSizes = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        p[i] = malloc(m * sizeof(int));
        (*returnColumnSizes)[i] = m;
    }

    long long suf = 1; // 后缀乘积
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            p[i][j] = suf; // p[i][j] 先初始化成后缀乘积
            suf = suf * grid[i][j] % MOD;
        }
    }

    long long pre = 1; // 前缀乘积
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            p[i][j] = p[i][j] * pre % MOD; // 乘上前缀乘积
            pre = pre * grid[i][j] % MOD;
        }
    }

    return p;
}

func constructProductMatrix(grid [][]int) [][]int {
const mod = 12345
n, m := len(grid), len(grid[0])
p := make([][]int, n)
suf := 1 // 后缀乘积
for i := n - 1; i >= 0; i-- {
p[i] = make([]int, m)
for j := m - 1; j >= 0; j-- {
p[i][j] = suf // p[i][j] 先初始化成后缀乘积
suf = suf * grid[i][j] % mod
}
}

pre := 1 // 前缀乘积
for i, row := range grid {
for j, x := range row {
p[i][j] = p[i][j] * pre % mod // 乘上前缀乘积
pre = pre * x % mod
}
}
return p
}

var constructProductMatrix = function(grid) {
    const MOD = 12345;
    const n = grid.length, m = grid[0].length;
    const p = Array.from({ length: n }, () => Array(m).fill(0));

    let suf = 1; // 后缀乘积
    for (let i = n - 1; i >= 0; i--) {
        for (let j = m - 1; j >= 0; j--) {
            p[i][j] = suf; // p[i][j] 先初始化成后缀乘积
            suf = suf * grid[i][j] % MOD;
        }
    }

    let pre = 1; // 前缀乘积
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            p[i][j] = p[i][j] * pre % MOD; // 乘上前缀乘积
            pre = pre * grid[i][j] % MOD;
        }
    }

    return p;
};

impl Solution {
    pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        const MOD: i64 = 12345;
        let n = grid.len();
        let m = grid[0].len();
        let mut p = vec![vec![0; m]; n];

        let mut suf = 1; // 后缀乘积
        for i in (0..n).rev() {
            for j in (0..m).rev() {
                p[i][j] = suf as i32; // p[i][j] 先初始化成后缀乘积
                suf = suf * grid[i][j] as i64 % MOD;
            }
        }

        let mut pre = 1; // 前缀乘积
        for i in 0..n {
            for j in 0..m {
                p[i][j] = (p[i][j] as i64 * pre % MOD) as i32; // 乘上前缀乘积
                pre = pre * grid[i][j] as i64 % MOD;
            }
        }

        p
    }
}

复杂度分析

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

专题训练

见下面动态规划题单的「专题：前后缀分解」。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

普通视图

一、贪心性质

二、寻找子问题

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

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

复杂度分析

五、1:1 翻译成递推

写法一

写法二

复杂度分析

六、单调队列优化

答疑

复杂度分析

七、空间优化

复杂度分析

专题训练

分类题单

方法一：从左到右遍历

复杂度分析

方法二：从 start 往两侧遍历

复杂度分析

思考题

分类题单

一、分析

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

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

复杂度分析

四、状态优化

复杂度分析

五、1:1 翻译成递推

复杂度分析

六、空间优化

复杂度分析

专题训练

分类题单

优化前

优化

复杂度分析

分类题单

算法一：暴力

算法二：差分数组（商分数组）

「平衡」两个算法

写法一

写法一的优化

复杂度分析

写法二

进一步优化

复杂度分析

分类题单

复杂度分析

分类题单

写法一

写法二

复杂度分析

分类题单

复杂度分析

分类题单

复杂度分析

如果有负数代价呢？

专题训练

分类题单

一、寻找子问题

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

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

优化前

优化

复杂度分析

四、1:1 翻译成递推

复杂度分析

五、空间优化

复杂度分析

六、双指针优化

复杂度分析

专题训练

分类题单

一、记忆化搜索

复杂度分析

二、1:1 翻译成递推

复杂度分析

三、空间优化