LeetCode 每日一题题解
五种方法：二分套二分 / k 指针 / 倍增 / DFS / 动态规划（Python/Java/C++/Go）endlesscheng
2025年2月23日 12:18

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

LeetCode 每日一题题解

作者 endlesscheng

2025年2月23日 12:18

问题转化

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

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

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

现在问题变成：

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

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

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

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

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

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

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

答疑

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

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

###py

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

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

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

###py

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

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

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

###java

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

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

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

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

###cpp

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

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

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

###go

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

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

复杂度分析

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

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

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

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

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

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

优化前

###py

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

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

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

###java

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

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

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

###cpp

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

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

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

###go

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

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

优化

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

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

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

###py

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

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

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

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

###java

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

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

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

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

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

###cpp

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

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

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

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

###go

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

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

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

复杂度分析

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

方法三：二分答案 + 倍增

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

前置知识：倍增讲解。

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

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

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

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

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

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

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

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

###py

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

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

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

###java

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

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

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

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

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

###cpp

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

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

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

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

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

###go

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

k-- // 往后跳 k-1 步，这里先减一，方便计算
highBit := bits.Len(uint(k)) - 1
nxt := make([][5]int, n+1) // 5 可以改为 highBit+1（用 array 而不是 slice，提高访问效率）
for j := range nxt[n] {
nxt[n][j] = n // 哨兵
}

ans := sort.Search(side*4/k, func(low int) bool {
low++
// 预处理倍增数组 nxt
j := n
for i := n - 1; i >= 0; i-- { // 转移来源在右边，要倒序计算
for a[j-1] >= a[i]+low {
j--
}
nxt[i][0] = j
for k := 1; k <= highBit; k++ {
nxt[i][k] = nxt[nxt[i][k-1]][k-1]
}
}

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

复杂度分析

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

方法四：二分答案 + 建树 + DFS

在方法三的双指针基础上，连一条从 $j$ 到 $i$ 的有向边，我们会得到一棵有向树，根是 $n$。

从 $n$ 开始递归这棵树，同时用一个栈记录从根到当前节点的 $a[x]$ 信息。

当栈中有 $k$ 个点时，记录栈中倒数第 $k$ 个数和栈顶的距离，如果 $\le \textit{side}\cdot 4 - \textit{low}$，则找到了满足要求的 $k$ 的点，结束递归。

⚠注意：无需判断 $f[i]>k$ 的情况，因为这意味着之前栈中有 $k$ 个点的时候，首尾两点间的距离足够远（甚至还可以再容纳一个点），一定满足要求。

###py

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

        def check(low: int) -> bool:
            g = [[] for _ in range(n + 1)]
            j = n
            for i in range(n - 1, -1, -1):
                while a[j - 1] >= a[i] + low:
                    j -= 1
                g[j].append(i)  # 建树

            st = []
            def dfs(x: int) -> bool:
                st.append(a[x])
                # 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
                if len(st) > k and st[-k] - a[x] <= side * 4 - low:
                    return True
                for y in g[x]:
                    if dfs(y):
                        return True
                st.pop()  # 恢复现场
                return False
            return dfs(n)

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

###java

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

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

    private boolean check(long[] a, int side, int k, int low) {
        int n = a.length - 1;
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = n - 1, j = n; i >= 0; i--) {
            while (a[j - 1] >= a[i] + low) {
                j--;
            }
            g[j].add(i); // 建树
        }

        List<Long> st = new ArrayList<>();
        return dfs(a, g, st, k, side * 4L - low, n);
    }

    private boolean dfs(long[] a, List<Integer>[] g, List<Long> st, int k, long limit, int x) {
        st.add(a[x]);
        int m = st.size();
        // 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
        if (m > k && st.get(m - k) - a[x] <= limit) {
            return true;
        }
        for (int y : g[x]) {
            if (dfs(a, g, st, k, limit, y)) {
                return true;
            }
        }
        st.remove(m - 1); // 恢复现场
        return false;
    }
}

###cpp

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

        auto check = [&](int low) -> bool {
            vector<vector<int>> g(n + 1);
            int j = n;
            for (int i = n - 1; i >= 0; i--) {
                while (a[j - 1] >= a[i] + low) {
                    j--;
                }
                g[j].push_back(i); // 建树
            }

            vector<long long> st;
            auto dfs = [&](this auto&& dfs, int x) -> bool {
                st.push_back(a[x]);
                int m = st.size();
                // 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
                if (m > k && st[m - k] - a[x] <= side * 4LL - low) {
                    return true;
                }
                for (int y : g[x]) {
                    if (dfs(y)) {
                        return true;
                    }
                }
                st.pop_back(); // 恢复现场
                return false;
            };
            return dfs(n);
        };

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

###go

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

g := make([][]int, n+1)
ans := sort.Search(side*4/k, func(low int) bool {
low++
clear(g)
j := n
for i := n - 1; i >= 0; i-- {
for a[j-1] >= a[i]+low {
j--
}
g[j] = append(g[j], i) // 建树
}

st := []int{}
var dfs func(int) bool
dfs = func(x int) bool {
st = append(st, a[x])
m := len(st)
// 注意栈中多了一个 a[n]，所以是 m > k 不是 ==
if m > k && st[m-k]-a[x] <= side*4-low {
return true
}
for _, y := range g[x] {
if dfs(y) {
return true
}
}
st = st[:m-1] // 恢复现场
return false
}
return !dfs(n)
})
return ans
}

复杂度分析

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

方法五：二分 + 动态规划

定义 $f[i]$ 表示从 $i$ 往后找，最多可以找多少个点（包含 $i$）。

设下一个点的下标为 $j$，那么有

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

初始值 $f[n] = 0$。

此外，定义 $\textit{end}[i]$ 表示从 $i$ 往后找，最后一个点的下标。

如果 $f[i]=1$，那么 $\textit{end}[i]$ 就是 $i$ 自己。
如果 $f[i]>1$，那么 $\textit{end}[i]$ 是从 $j$ 往后找，最后一个点的下标，即 $\textit{end}[j]$。

所以有

$$
\textit{end}[i] =
\begin{cases}
i, & f[i]=1 \
\textit{end}[j], & f[i]>1 \
\end{cases}
$$

如果 $f[i]=k$，且首尾两点的距离 $a[\textit{end}[i]] - a[i] \le \textit{side}\cdot 4 - \textit{low}$，那么满足要求，返回。

⚠注意：无需判断 $f[i]>k$ 的情况。证明：每次间隔至少 $\textit{low}$ 才会把 $f[i]$ 加 $1$，如果出现 $f[i]=f[j]+1=k+1$ 的情况，说明我们在 $f[j]=k$ 的基础上增加了一个点，对于 $f[j]$ 来说，首尾节点有足够的间距（比 $\textit{low}$ 还大），使得我们可以再加一个点进来，得到 $f[i]=k+1$。所以 $f[j]=k$ 的时候必然可以满足要求，我们不会继续循环到 $f[i]=k+1$ 的情况。

###py

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

        n = len(a)
        f = [0] * (n + 1)
        end = [0] * n

        def check(low: int) -> bool:
            j = n
            for i in range(n - 1, -1, -1):
                while a[j - 1] >= a[i] + low:
                    j -= 1
                f[i] = f[j] + 1
                end[i] = end[j] if f[i] > 1 else i
                if f[i] == k and a[end[i]] - a[i] <= side * 4 - low:
                    return True
            return False

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

###java

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

        int[] f = new int[n + 1];
        int[] end = new int[n];

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

    private boolean check(long[] a, int side, int k, int low, int[] f, int[] end) {
        int n = a.length;
        for (int i = n - 1, j = n; i >= 0; i--) {
            while (a[j - 1] >= a[i] + low) {
                j--;
            }
            f[i] = f[j] + 1;
            end[i] = f[i] > 1 ? end[j] : i;
            if (f[i] == k && a[end[i]] - a[i] <= side * 4L - low) {
                return true;
            }
        }
        return false;
    }
}

###cpp

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

        int n = a.size();
        vector<int> f(n + 1), end(n);

        auto check = [&](int low) -> bool {
            int j = n;
            for (int i = n - 1; i >= 0; i--) {
                while (a[j - 1] >= a[i] + low) {
                    j--;
                }
                f[i] = f[j] + 1;
                end[i] = f[i] > 1 ? end[j] : i;
                if (f[i] == k && a[end[i]] - a[i] <= side * 4LL - low) {
                    return true;
                }
            }
            return false;
        };

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

###go

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

f := make([]int, n+1)
end := make([]int, n)

ans := sort.Search(side*4/k, func(low int) bool {
low++
j := n
for i := n - 1; i >= 0; i-- {
for a[j-1] >= a[i]+low {
j--
}
f[i] = f[j] + 1
if f[i] == 1 {
end[i] = i // i 自己就是最后一个点
} else {
end[i] = end[j]
}
if f[i] == k && a[end[i]]-a[i] <= side*4-low {
return false
}
}
return true
})
return ans
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
贪心（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2023年8月27日 12:15

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

LeetCode 每日一题题解

作者 endlesscheng

2023年8月27日 12:15

示例 2 的 $\textit{moves} = \texttt{_R__LL_}$：

先只看 $\texttt{R}$ 和 $\texttt{L}$，往右走了 $1$ 步，再往左走 $2$ 步，相当于往左走了 $1$ 步，位于数轴的 $-1$。
还剩下 $4$ 个 $\texttt{_}$，怎么走最优？当然是继续往左走啦，继续往左走 $4$ 步，最终位于 $-5$。

设 $\textit{cntR}$ 为 $\texttt{R}$ 的个数，$\textit{cntL}$ 为 $\texttt{L}$ 的个数，那么 $\texttt{_}$ 的个数为 $n - \textit{cntR} - \textit{cntL}$。先只看 $\texttt{R}$ 和 $\texttt{L}$，我们到原点的距离为 $|\textit{cntR} - \textit{cntL}|$。然后继续走 $n - \textit{cntR} - \textit{cntL}$ 步，最终答案为

$$
|\textit{cntR} - \textit{cntL}| + n - \textit{cntR} - \textit{cntL}
$$

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        cnt_r = moves.count('R')
        cnt_l = moves.count('L')
        return abs(cnt_r - cnt_l) + len(moves) - cnt_r - cnt_l

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int cntR = 0;
        int cntL = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'R') {
                cntR++;
            } else if (c == 'L') {
                cntL++;
            }
        }
        return Math.abs(cntR - cntL) + moves.length() - cntR - cntL;
    }
}

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int cnt_r = ranges::count(moves, 'R');
        int cnt_l = ranges::count(moves, 'L');
        return abs(cnt_r - cnt_l) + moves.size() - cnt_r - cnt_l;
    }
};

int furthestDistanceFromOrigin(char* moves) {
    int cnt_r = 0;
    int cnt_l = 0;
    int i = 0;
    for (; moves[i]; i++) {
        if (moves[i] == 'R') {
            cnt_r++;
        } else if (moves[i] == 'L') {
            cnt_l++;
        }
    }
    return abs(cnt_r - cnt_l) + i - cnt_r - cnt_l;
}

func furthestDistanceFromOrigin(moves string) int {
cntR := strings.Count(moves, "R")
cntL := strings.Count(moves, "L")
return abs(cntR-cntL) + len(moves) - cntR - cntL
}

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

var furthestDistanceFromOrigin = function(moves) {
    const cntR = [...moves].filter(c => c === 'R').length;
    const cntL = [...moves].filter(c => c === 'L').length;
    return Math.abs(cntR - cntL) + moves.length - cntR - cntL;
};

impl Solution {
    pub fn furthest_distance_from_origin(moves: String) -> i32 {
        let cnt_r = moves.bytes().filter(|&c| c == b'R').count() as i32;
        let cnt_l = moves.bytes().filter(|&c| c == b'L').count() as i32;
        (cnt_r - cnt_l).abs() + moves.len() as i32 - cnt_r - cnt_l
    }
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
两种 O(n) 方法：照搬 2602 / 考虑距离之和的增量endlesscheng
2023年4月9日 12:31

两种 O(n) 方法：照搬 2602 / 考虑距离之和的增量

LeetCode 每日一题题解

作者 endlesscheng

2023年4月9日 12:31

本题视频讲解

见【周赛 340】。

方法一：相同元素分组+前缀和

按照相同元素分组后再计算。

这里的思路和 2602. 使数组元素全部相等的最少操作次数（题解）是一样的。由于目标位置就是数组中的下标，无需二分。

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            groups[x].append(i)  # 相同元素分到同一组，记录下标
        ans = [0] * len(nums)
        for a in groups.values():
            n = len(a)
            s = list(accumulate(a, initial=0))  # 前缀和
            for j, target in enumerate(a):
                left = target * j - s[j]  # 蓝色面积
                right = s[n] - s[j] - target * (n - j)  # 绿色面积
                ans[target] = left + right
        return ans

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        var groups = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; ++i) // 相同元素分到同一组，记录下标
            groups.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);

        var ans = new long[n];
        var s = new long[n + 1];
        for (var a : groups.values()) {
            int m = a.size();
            for (int i = 0; i < m; ++i)
                s[i + 1] = s[i] + a.get(i); // 前缀和
            for (int i = 0; i < m; ++i) {
                int target = a.get(i);
                long left = (long) target * i - s[i]; // 蓝色面积
                long right = s[m] - s[i] - (long) target * (m - i); // 绿色面积
                ans[target] = left + right;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[nums[i]].push_back(i); // 相同元素分到同一组，记录下标

        vector<long long> ans(n);
        long long s[n + 1];
        s[0] = 0;
        for (auto& [_, a]: groups) {
            int m = a.size();
            for (int i = 0; i < m; ++i)
                s[i + 1] = s[i] + a[i]; // 前缀和
            for (int i = 0; i < m; ++i) {
                long long target = a[i];
                long long left = target * i - s[i]; // 蓝色面积
                long long right = s[m] - s[i] - target * (m - i); // 绿色面积
                ans[target] = left + right;
            }
        }
        return ans;
    }
};

func distance(nums []int) []int64 {
groups := map[int][]int{}
for i, x := range nums {
groups[x] = append(groups[x], i) // 相同元素分到同一组，记录下标
}
ans := make([]int64, len(nums))
for _, a := range groups {
n := len(a)
s := make([]int, n+1)
for i, x := range a {
s[i+1] = s[i] + x // 前缀和
}
for i, target := range a {
left := target*i - s[i] // 蓝色面积
right := s[n] - s[i] - target*(n-i) // 绿色面积
ans[target] = int64(left + right)
}
}
return ans
}

复杂度分析

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

方法二：相同元素分组+考虑增量

分组后，对于其中一个组 $a$，我们先暴力计算出 $a[0]$ 到其它元素的距离之和，设为 $s_0$。

然后计算 $a[1]$ 到其它元素的距离之和 $s_1$。我们不再暴力计算，而是思考：从 $s_0$ 到 $s_1$，这个增量 $s_1-s_0$ 是多少？（增量可以是负数）

设 $n$ 为 $a$ 的长度，从 $s_0$ 到 $s_1$，有 $1$ 个数的距离变大了 $a[1]-a[0]$（原来是到 $a[0]$ 的距离，现在是到 $a[1]$ 的距离；原来是 $a[0]$ 到 $a[0]$ 的距离为 $0$，现在是 $a[0]$ 到 $a[1]$ 的距离为 $a[1]-a[0]$），其余 $n-1$ 个数的距离变小了 $a[1]-a[0]$（原来是到 $a[0]$ 的距离，现在是到 $a[1]$ 的距离）。

所以对于 $s_1$，我们可以 $\mathcal{O}(1)$ 地知道 $a[1]$ 到其它元素的距离之和为

$$
s_0 + (2-n) \cdot (a[1]-a[0])
$$

一般地，设 $a[i-1]$ 到其它元素的距离之和为 $s$，那么 $a[i]$ 到其它元素的距离之和为

$$
s + (2i-n) \cdot (a[i]-a[i-1])
$$

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            groups[x].append(i)  # 相同元素分到同一组，记录下标
        ans = [0] * len(nums)
        for a in groups.values():
            n = len(a)
            s = sum(x - a[0] for x in a)  # a[0] 到其它下标的距离之和
            ans[a[0]] = s
            for i in range(1, n):
                # 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                s += (i * 2 - n) * (a[i] - a[i - 1])
                ans[a[i]] = s
        return ans

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        var groups = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; ++i) // 相同元素分到同一组，记录下标
            groups.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);

        var ans = new long[n];
        for (var a : groups.values()) {
            int m = a.size();
            long s = 0;
            for (int x : a)
                s += x - a.get(0); // a[0] 到其它下标的距离之和
            ans[a.get(0)] = s;
            for (int i = 1; i < m; ++i)
                // 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                ans[a.get(i)] = s += (long) (i * 2 - m) * (a.get(i) - a.get(i - 1));
        }
        return ans;
    }
}

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[nums[i]].push_back(i); // 相同元素分到同一组，记录下标

        vector<long long> ans(n);
        for (auto& [_, a]: groups) {
            int m = a.size();
            long long s = 0;
            for (int x: a)
                s += x - a[0]; // a[0] 到其它下标的距离之和
            ans[a[0]] = s;
            for (int i = 1; i < m; ++i)
                // 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
                ans[a[i]] = s += (long long) (i * 2 - m) * (a[i] - a[i - 1]);
        }
        return ans;
    }
};

func distance(nums []int) []int64 {
groups := map[int][]int{}
for i, x := range nums {
groups[x] = append(groups[x], i) // 相同元素分到同一组，记录下标
}
ans := make([]int64, len(nums))
for _, a := range groups {
n := len(a)
s := int64(0)
for _, x := range a {
s += int64(x - a[0]) // a[0] 到其它下标的距离之和
}
ans[a[0]] = s
for i := 1; i < n; i++ {
// 从计算 a[i-1] 到计算 a[i]，考虑 s 增加了多少
s += int64(i*2-n) * int64(a[i]-a[i-1])
ans[a[i]] = s
}
}
return ans
}

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
暴力（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2022年10月30日 07:58

暴力（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2022年10月30日 07:58

对于每个 $q = \textit{queries}[i]$，遍历 $\textit{dictionary}$ 中的字符串 $s$，判断 $q$ 和 $s$ 是否至多有两个位置上的字母不同。

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for q in queries:
            for s in dictionary:
                if sum(x != y for x, y in zip(q, s)) <= 2:
                    ans.append(q)
                    break
        return ans

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> ans = new ArrayList<>();
        for (String q : queries) {
            for (String s : dictionary) {
                int cnt = 0;
                for (int i = 0; i < s.length() && cnt <= 2; i++) {
                    if (q.charAt(i) != s.charAt(i)) {
                        cnt++;
                    }
                }
                if (cnt <= 2) {
                    ans.add(q);
                    break;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for (auto& q : queries) {
            for (auto& s : dictionary) {
                int cnt = 0;
                for (int i = 0; i < s.size() && cnt <= 2; i++) {
                    if (q[i] != s[i]) {
                        cnt++;
                    }
                }
                if (cnt <= 2) {
                    ans.push_back(q);
                    break;
                }
            }
        }
        return ans;
    }
};

char** twoEditWords(char** queries, int queriesSize, char** dictionary, int dictionarySize, int* returnSize) {
    char** ans = malloc(queriesSize * sizeof(char*));
    *returnSize = 0;

    for (int i = 0; i < queriesSize; i++) {
        char* q = queries[i];
        for (int j = 0; j < dictionarySize; j++) {
            char* s = dictionary[j];
            int cnt = 0;
            for (int k = 0; s[k] && cnt <= 2; k++) {
                if (q[k] != s[k]) {
                    cnt++;
                }
            }
            if (cnt <= 2) {
                ans[(*returnSize)++] = q;
                break;
            }
        }
    }

    return ans;
}

func twoEditWords(queries, dictionary []string) (ans []string) {
for _, q := range queries {
next:
for _, s := range dictionary {
cnt := 0
for i := range s {
if q[i] != s[i] {
cnt++
if cnt > 2 {
continue next
}
}
}
ans = append(ans, q)
break
}
}
return
}

var twoEditWords = function(queries, dictionary) {
    const ans = [];
    for (const q of queries) {
        for (const s of dictionary) {
            let cnt = 0;
            for (let i = 0; i < s.length && cnt <= 2; i++) {
                if (q[i] !== s[i]) {
                    cnt++;
                }
            }
            if (cnt <= 2) {
                ans.push(q);
                break;
            }
        }
    }
    return ans;
};

impl Solution {
    pub fn two_edit_words(queries: Vec<String>, dictionary: Vec<String>) -> Vec<String> {
        let mut ans = vec![];
        for q in queries {
            for s in &dictionary {
                let mut cnt = 0;
                for (a, b) in q.bytes().zip(s.bytes()) {
                    if a != b {
                        cnt += 1;
                        if cnt > 2 {
                            break;
                        }
                    }
                }
                if cnt <= 2 {
                    ans.push(q);
                    break;
                }
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(qdn)$，其中 $q$ 是 $\textit{queries}$ 的长度，$d$ 是 $\textit{dictionary}$ 的长度，$n$ 是 $\textit{queries}[i]$ 的长度。题目保证所有字符串长度相等。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
建图 + DFS（Python/Java/C++/Go）endlesscheng
2026年4月14日 08:20

建图 + DFS（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年4月14日 08:20

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

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

证明（具体交换方案）

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

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

###py

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

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

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

###java

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

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

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

###cpp

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

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

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

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

###go

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

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

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

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

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

复杂度分析

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

相似题目

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
O(n) 做法，脑筋急转弯（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2021年11月21日 12:18

O(n) 做法，脑筋急转弯（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2021年11月21日 12:18

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

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

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

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

答案为二者的最大值

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

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

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

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

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

        return max(r, n - 1 - l)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

复杂度分析

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

专题训练

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

LeetCode 每日一题题解
双指针（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2021年5月9日 12:09

双指针（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2021年5月9日 12:09

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

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

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

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

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

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

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

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

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

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

复杂度分析

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

专题训练

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

反转数字（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年12月21日 12:25

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

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

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

###py

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

###py

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

###java

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

###cpp

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

###go

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

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

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

枚举右，维护左（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年11月30日 12:07

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

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

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

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

###py

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

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

        return ans if ans < inf else -1

###py

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

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

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

        return ans if ans < inf else -1

###java

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

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

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

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

###cpp

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

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

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

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

###go

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

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

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

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

复杂度分析

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

专题训练

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

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
两种方法：二分查找 / 预处理（Python/Java/C++/Go）endlesscheng
2025年3月16日 12:10

两种方法：二分查找 / 预处理（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年3月16日 12:10

方法一：二分查找

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

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

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

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

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

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

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

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

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

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

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

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

###py

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

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

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

###java

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

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

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

###cpp

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

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

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

###go

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

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

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

复杂度分析

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

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

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

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

计算方式：

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

答案为：

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

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

优化前

###py

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

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

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

###java

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

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

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

###cpp

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

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

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

###go

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

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

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

优化（一）

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

###py

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

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

###java

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

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

###cpp

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

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

###go

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

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

优化（二）

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

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

###py

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

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

###java

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

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

###cpp

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

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

###go

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

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

复杂度分析

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

相似题目

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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站@灵茶山艾府

普通视图

问题转化

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

答疑

复杂度分析

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

优化前

优化

复杂度分析

方法三：二分答案 + 倍增

复杂度分析

方法四：二分答案 + 建树 + DFS

复杂度分析

方法五：二分 + 动态规划

复杂度分析

分类题单

复杂度分析

分类题单

本题视频讲解

方法一：相同元素分组+前缀和

复杂度分析

方法二：相同元素分组+考虑增量

复杂度分析

分类题单

复杂度分析

分类题单

复杂度分析

相似题目

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

分类题单

复杂度分析

专题训练

分类题单

方法一：二分查找

复杂度分析

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

优化前

优化（一）

优化（二）

复杂度分析

相似题目

分类题单

一、贪心性质

二、寻找子问题

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

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

复杂度分析

五、1:1 翻译成递推

写法一

写法二

复杂度分析

六、单调队列优化

答疑

复杂度分析

七、空间优化

复杂度分析

专题训练

分类题单

方法一：从左到右遍历

复杂度分析

方法二：从 start 往两侧遍历

复杂度分析

思考题

分类题单

一、分析

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

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

复杂度分析

四、状态优化

复杂度分析

五、1:1 翻译成递推

复杂度分析

六、空间优化