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），从而得到每个位置可能达到的最大距离上界。最终，取所有位置中的最大值作为答案。

大体步骤

1. 初始化变量：

   • 设置当前位置坐标 (x, y) 为原点 (0, 0)，表示起始位置。
   • 初始化 max_distance 为 0，用于记录整个过程中可能的最大曼哈顿距离。

2. 遍历移动序列：

   • 对于字符串 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。

3. 返回结果：

   • 遍历所有字符后，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 main

import (
	"fmt"
)

func maxDistance(s string, k int) int {
	latitude, longitude, ans := 0, 0, 0
	n := 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 := 3
	result := maxDistance(s, k)
	fmt.Println(result)
}

Python完整代码如下：

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

def max_distance(s: str, k: int) -> int:
    latitude = 0
    longitude = 0
    ans = 0

    for i, ch in enumerate(s):
        if ch == 'N':
            latitude += 1
        elif ch == 'S':
            latitude -= 1
        elif ch == 'E':
            longitude += 1
        elif ch == 'W':
            longitude -= 1

        current = abs(latitude) + abs(longitude) + k * 2
        # 距离不可能超过已走的步数 i+1
        candidate = min(current, i + 1)
        ans = max(ans, candidate)

    return ans

if __name__ == "__main__":
    s = "NSWWEW"
    k = 3
    result = max_distance(s, k)
    print(result)