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

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完整代码如下：

packagemainimport("fmt")funcmaxDistance(movesstring)int{x,y,free:=0,0,0for_,ch:=rangemoves{switchch{case'L':x--case'R':x++case'D':y--case'U':y++default:free++}}returnabs(x)+abs(y)+free}funcabs(xint)int{ifx<0{return-x}returnx}funcmain(){moves:="L_D_"result:=maxDistance(moves)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defmax_distance(moves:str)->int:x=0y=0free=0forchinmoves:ifch=='L':x-=1elifch=='R':x+=1elifch=='D':y-=1elifch=='U':y+=1else:free+=1returnabs(x)+abs(y)+freeif__name__=="__main__":moves="L_D_"result=max_distance(moves)print(result)

C++完整代码如下：

#include#include#includeintmaxDistance(conststd::string&moves){intx=0,y=0,free=0;for(charch:moves){switch(ch){case'L':--x;break;case'R':++x;break;case'D':--y;break;case'U':++y;break;default:++free;break;}}returnstd::abs(x)+std::abs(y)+free;}intmain(){std::string moves="L_D_";intresult=maxDistance(moves);std::cout<<result<<std::endl;return0;}