2025-08-12：K次修改后的最大曼哈顿距离。用go语言，给出一个只包含字符 'N'、'S'、'E'、'W' 的字符串 s，

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. 1. 初始化变量：
   • • 设置当前位置坐标 (x, y) 为原点 (0, 0)，表示起始位置。
   • • 初始化 max_distance 为 0，用于记录整个过程中可能的最大曼哈顿距离。
2. 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. 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-*-

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

    for i, ch inenumerate(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)