当前位置：首页 > news >正文

2025-08-12：K次修改后的最大曼哈顿距离。用go语言，给出一个只包含字符 ‘N‘、‘S‘、‘E‘、‘W‘ 的字符串 s，每个字符表示在无界方格上向某个方向移动一步。起点为原点 (0,0)。你可

news 2025/8/28 11:09:58

2025-08-12：K次修改后的最大曼哈顿距离。用go语言，给出一个只包含字符 'N'、'S'、'E'、'W' 的字符串 s，每个字符表示在无界方格上向某个方向移动一步。起点为原点 (0,0)。你可以最多改变 s 中的 k 个字符，每个被改的字符可以变为四个方向中的任意一个。按修改后的顺序依次执行这些步子，考虑整个移动过程中的任意时刻（即任意一步之后），求能够达到的离原点的最大曼哈顿距离（横坐标差的绝对值与纵坐标差的绝对值之和）。请返回这个最大可能值。

1 <= s.length <= 100000。

0 <= k <= s.length。

s 仅由 'N'、'S'、'E' 和 'W' 。

输入：s = "NSWWEW", k = 3。

输出：6。

解释：

将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。

执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

题目来自力扣3443。

解决过程

以下描述算法的整体思路和步骤，不涉及具体代码实现。算法的核心思想是：在原始移动序列的基础上，通过计算每个位置（即每步之后）的原始曼哈顿距离，并考虑最多 k 次修改所能带来的最大增益（每次修改最多可使曼哈顿距离增加 2），从而得到每个位置可能达到的最大距离上界。最终，取所有位置中的最大值作为答案。

大体步骤

初始化变量：
- 设置当前位置坐标 (x, y) 为原点 (0, 0)，表示起始位置。
- 初始化 max_distance 为 0，用于记录整个过程中可能的最大曼哈顿距离。
遍历移动序列：
- 对于字符串 s 中的每个字符（按顺序处理），执行以下操作：
  - 更新当前位置：根据当前字符（未修改的方向）更新坐标：
    - 如果字符是 'N'，则 y 增加 1（向北移动）。
    - 如果字符是 'S'，则 y 减少 1（向南移动）。
    - 如果字符是 'E'，则 x 增加 1（向东移动）。
    - 如果字符是 'W'，则 x 减少 1（向西移动）。
    - 这一步得到的是原始序列下的当前位置 (x, y)。
  - 计算原始曼哈顿距离：计算当前位置的原始曼哈顿距离，即 dist = |x| + |y|。这表示在未修改序列时，该步后的距离。
  - 计算当前可能的最大距离：考虑最多 k 次修改的影响：
    - 每个修改最多可以使曼哈顿距离增加 2（例如，在适当位置将向原点方向移动改为远离原点方向）。
    - 因此，修改后该位置可能的最大距离上界是 dist + 2 * k。
    - 同时，由于已经执行了 step_count 步（当前是第 i+1 步，其中 i 是当前字符索引，从 0 开始），曼哈顿距离不可能超过步数（因为每步最多增加距离 1）。
    - 因此，该位置的最大距离候选值为 min(dist + 2 * k, step_count)，其中 step_count = i + 1（因为索引 i 对应第 i+1 步）。
  - 更新全局最大距离：将候选值与当前 max_distance 比较，取较大者更新 max_distance。
返回结果：
- 遍历所有字符后，max_distance 即为所求的最大曼哈顿距离。

关键点解释

为什么考虑原始位置？：算法使用原始序列的当前位置作为基准，因为修改后的位置虽可能不同，但曼哈顿距离的差值最多为 2 * k（每次修改最多带来 2 的增益）。因此，dist + 2 * k 是修改后距离的上界。
为什么与步数取最小值？：曼哈顿距离不可能超过已执行的步数（因为每步最多使 |x| 或 |y| 增加 1）。因此，候选值受 step_count 限制。
为什么在每一步后计算？：最大距离可能出现在任意一步之后（不一定是最后一步）。通过遍历每个位置，算法覆盖了所有可能的时间点。
正确性保证：在最优修改策略下，这个上界是可达到的（例如，通过将修改用于在关键位置将移动方向改为远离原点）。例如，在 s = "NSWWEW", k = 3 中，算法在最后一步计算原始距离为 2，候选值 min(2 + 6, 6) = 6，与最优修改结果一致。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。算法只需遍历字符串一次，每次操作（更新坐标、计算距离、比较等）都是常数时间 O(1)。
额外空间复杂度：O(1)。算法仅使用固定数量的额外变量（如 x、y、max_distance、循环索引等），不依赖于输入大小。

该算法高效且简洁，适用于约束条件（n ≤ 100,000）。

Go完整代码如下：

package mainimport ("fmt"
)func maxDistance(s string, k int) int {latitude, longitude, ans := 0, 0, 0n := len(s)for i := 0; i < n; i++ {switch s[i] {case 'N':latitude++case 'S':latitude--case 'E':longitude++case 'W':longitude--}ans = max(ans, min(abs(latitude)+abs(longitude)+k*2, i+1))}return ans
}func abs(x int) int {if x < 0 {return -x}return x
}func main() {s := "NSWWEW"k := 3result := maxDistance(s, k)fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-def max_distance(s: str, k: int) -> int:latitude = 0longitude = 0ans = 0for i, ch in enumerate(s):if ch == 'N':latitude += 1elif ch == 'S':latitude -= 1elif ch == 'E':longitude += 1elif ch == 'W':longitude -= 1current = abs(latitude) + abs(longitude) + k * 2# 距离不可能超过已走的步数 i+1candidate = min(current, i + 1)ans = max(ans, candidate)return ansif __name__ == "__main__":s = "NSWWEW"k = 3result = max_distance(s, k)print(result)

在这里插入图片描述