2026-09-25：移动后的最大曼哈顿距离。用go语言，给定一个仅包含 U、D、L、R、_ 这几种字符的字符串 moves。 起始位置是二维坐标 (0, 0)

2026-09-25：移动后的最大曼哈顿距离。用go语言，给定一个仅包含 U、D、L、R、_ 这几种字符的字符串 moves。

起始位置是二维坐标 (0, 0)。每读到一个字符，就进行一次移动：

U 表示纵坐标增加 1。

D 表示纵坐标减少 1。

L 表示横坐标减少 1。

R 表示横坐标增加 1。

_ 是一个可自由选择的占位符，每个下划线都可以单独改成 U、D、L、R 中的任意一种。

把字符串中的所有移动都执行完之后，会到达某个终点。要求求出这个终点到起始点 (0, 0) 的曼哈顿距离可能达到的最大值。

曼哈顿距离的计算方式是：对于两个点 (x1, y1) 和 (x2, y2)，距离等于 |x1 – x2| + |y1 – y2|。

1 <= moves.length <= 100000。

moves 仅由 ‘U’、’D’、’L’、’R’ 和 ‘_’ 组成。

输入： moves = “L_D_”。

输出： 4。

解释：

一种最优选择为：

‘L’：(0, 0) -> (-1, 0)

将 ‘_’ 视为 ‘D’：(-1, 0) -> (-1, -1)

‘D’：(-1, -1) -> (-1, -2)

将 ‘_’ 视为 ‘L’：(-1, -2) -> (-2, -2)

最终位置到原点的曼哈顿距离为 |0 – (-2)| + |0 – (-2)| = 4。

题目来自力扣3968。

大体步骤如下：

1. 一开始，把当前位置看作原点，也就是横坐标和纵坐标都从 0 开始。同时准备一个计数，用来记录遇到了多少个下划线字符。

2. 然后从左到右依次读取字符串中的每一个字符。读取过程中，只处理已经明确的移动方向，而下划线先不决定具体方向。

3. 如果当前字符是 L，就让横坐标减少 1，纵坐标不变。
如果当前字符是 R，就让横坐标增加 1，纵坐标不变。
如果当前字符是 D，就让纵坐标减少 1，横坐标不变。
如果当前字符是 U，就让纵坐标增加 1，横坐标不变。
如果当前字符是下划线，就暂时不改变横纵坐标，只把“自由移动次数”加一。

4. 这样完整扫描一遍字符串之后，所有非下划线字符造成的最终横纵坐标已经确定下来，记作一个基础终点。所有下划线还没有分配方向，但它们已经被统计成一个自由移动的总数。

5. 接下来考虑这些下划线怎样选择方向，才能让最终位置离原点尽可能远。曼哈顿距离等于最终横坐标的绝对值加上最终纵坐标的绝对值。每把一个下划线分配到横坐标方向或者纵坐标方向，都可以让它沿着当前坐标绝对值增大的方向移动。
也就是说，如果当前横坐标是正的，就可以把下划线选成 R，让横坐标更大；如果当前横坐标是负的，就选成 L，让横坐标更小。纵坐标也是同样道理。
因此，每一个下划线字符最多能让曼哈顿距离增加 1，而且一定可以做到增加 1。所以所有下划线带来的总增益，正好等于下划线的数量。

6. 于是，最终能够达到的最大曼哈顿距离，就是非下划线字符已经形成的固定终点到原点的曼哈顿距离，再加上所有下划线的数量。
用描述性说法就是：先算出固定移动造成的横坐标绝对值与纵坐标绝对值之和，再把这个和加上自由下划线的个数。

7. 以题目中的例子 “L_D_” 来看：

• 读到 L，横坐标变成 -1，纵坐标仍是 0。

• 读到一个下划线，自由次数变成 1。

• 读到 D，纵坐标变成 -1。

• 又读到一个下划线，自由次数变成 2。
扫描结束后，固定部分到达 (-1, -1)，它到原点的曼哈顿距离是 1 + 1 = 2。自由下划线一共有 2 个，每个都能让距离再增加 1，所以最大距离是 2 + 2 = 4。这与题目给出的输出一致。

8. 这个过程中，字符串只会被从头到尾扫描一次。每次处理一个字符时，只做一些判断和加减操作，不需要嵌套循环，也不需要额外保存复杂结构。

因此：

总的时间复杂度是 O(n)，其中 n 是字符串 moves 的长度。
总的额外空间复杂度是 O(1)，因为除了输入字符串本身之外，只使用了常数个额外变量来保存横坐标、纵坐标和自由下划线数量。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func maxDistance(moves string)int {
    x, y, free := 0, 0, 0

     for _, ch := range moves {
        switch ch {
        case'L':
            x--
        case'R':
            x++
        case'D':
            y--
        case'U':
            y++
        default:
            free++
        }
    }

     return abs(x) + abs(y) + free
}

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

 func main() {
    moves := "L_D_"
    result := maxDistance(moves)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def max_distance(moves: str) -> int:
    x = 0
    y = 0
    free = 0

     for ch in moves:
        if ch == 'L':
            x -= 1
        elif ch == 'R':
            x += 1
        elif ch == 'D':
            y -= 1
        elif ch == 'U':
            y += 1
        else:
            free += 1

     return abs(x) + abs(y) + free

 if __name__ == "__main__":
    moves = "L_D_"
    result = max_distance(moves)
    print(result)

C++完整代码如下：

  

  


 int maxDistance(const std::string& moves) {
    int x = 0, y = 0, free = 0;

     for (char ch : moves) {
        switch (ch) {
        case'L':
            --x;
            break;
        case'R':
            ++x;
            break;
        case'D':
            --y;
            break;
        case'U':
            ++y;
            break;
        default:
            ++free;
            break;
        }
    }

     return std::abs(x) + std::abs(y) + free;
}

 int main() {
    std::string moves = "L_D_";
    int result = maxDistance(moves);
    std::cout << result << std::endl;

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。