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。大体步骤如下一开始把当前位置看作原点也就是横坐标和纵坐标都从 0 开始。同时准备一个计数用来记录遇到了多少个下划线字符。然后从左到右依次读取字符串中的每一个字符。读取过程中只处理已经明确的移动方向而下划线先不决定具体方向。如果当前字符是 L就让横坐标减少 1纵坐标不变。如果当前字符是 R就让横坐标增加 1纵坐标不变。如果当前字符是 D就让纵坐标减少 1横坐标不变。如果当前字符是 U就让纵坐标增加 1横坐标不变。如果当前字符是下划线就暂时不改变横纵坐标只把“自由移动次数”加一。这样完整扫描一遍字符串之后所有非下划线字符造成的最终横纵坐标已经确定下来记作一个基础终点。所有下划线还没有分配方向但它们已经被统计成一个自由移动的总数。接下来考虑这些下划线怎样选择方向才能让最终位置离原点尽可能远。曼哈顿距离等于最终横坐标的绝对值加上最终纵坐标的绝对值。每把一个下划线分配到横坐标方向或者纵坐标方向都可以让它沿着当前坐标绝对值增大的方向移动。也就是说如果当前横坐标是正的就可以把下划线选成 R让横坐标更大如果当前横坐标是负的就选成 L让横坐标更小。纵坐标也是同样道理。因此每一个下划线字符最多能让曼哈顿距离增加 1而且一定可以做到增加 1。所以所有下划线带来的总增益正好等于下划线的数量。于是最终能够达到的最大曼哈顿距离就是非下划线字符已经形成的固定终点到原点的曼哈顿距离再加上所有下划线的数量。用描述性说法就是先算出固定移动造成的横坐标绝对值与纵坐标绝对值之和再把这个和加上自由下划线的个数。以题目中的例子 “L_D_” 来看读到 L横坐标变成 -1纵坐标仍是 0。读到一个下划线自由次数变成 1。读到 D纵坐标变成 -1。又读到一个下划线自由次数变成 2。扫描结束后固定部分到达 (-1, -1)它到原点的曼哈顿距离是 1 1 2。自由下划线一共有 2 个每个都能让距离再增加 1所以最大距离是 2 2 4。这与题目给出的输出一致。这个过程中字符串只会被从头到尾扫描一次。每次处理一个字符时只做一些判断和加减操作不需要嵌套循环也不需要额外保存复杂结构。因此总的时间复杂度是 O(n)其中 n 是字符串 moves 的长度。总的额外空间复杂度是 O(1)因为除了输入字符串本身之外只使用了常数个额外变量来保存横坐标、纵坐标和自由下划线数量。Go完整代码如下packagemainimport(fmt)funcmaxDistance(movesstring)int{x,y,free:0,0,0for_,ch:rangemoves{switchch{caseL:x--caseR:xcaseD:y--caseU:ydefault:free}}returnabs(x)abs(y)free}funcabs(xint)int{ifx0{return-x}returnx}funcmain(){moves:L_D_result:maxDistance(moves)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmax_distance(moves:str)-int:x0y0free0forchinmoves:ifchL:x-1elifchR:x1elifchD:y-1elifchU:y1else:free1returnabs(x)abs(y)freeif__name____main__:movesL_D_resultmax_distance(moves)print(result)C完整代码如下#includeiostream#includestring#includecstdlibintmaxDistance(conststd::stringmoves){intx0,y0,free0;for(charch:moves){switch(ch){caseL:--x;break;caseR:x;break;caseD:--y;break;caseU:y;break;default:free;break;}}returnstd::abs(x)std::abs(y)free;}intmain(){std::string movesL_D_;intresultmaxDistance(moves);std::coutresultstd::endl;return0;}