目标
给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：
- 'N'：向北移动 1 个单位。
- 'S'：向南移动 1 个单位。
- 'E'：向东移动 1 个单位。
- 'W'：向西移动 1 个单位。
初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。
请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。
曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。
示例 1：
输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
移动操作 位置 (x, y) 曼哈顿距离 最大值
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。示例 2：
输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。说明：
- 1 <= s.length <= 10^5
- 0 <= k <= s.length
- s 仅由 'N'、'S'、'E' 和 'W' 。
思路
从原点 (0, 0) 出发，根据操作序列 s 朝四个方向移动，最多可以修改序列中 k 个方向，求能够到达的距离原点的最大曼哈顿距离。
遍历过程中记录距离变小的次数，每修改一次可以使得最大距离加 2。
网友指出每走一步可能增大的距离最多为 2 * k，但是不能超过往一个方向一直走的情况，即当前走的步数 i + 1。
代码
/**
* @date 2025-06-20 21:47
*/
public class MaxDistance3443 {
private static final Map<Character, int[]> MAP = new HashMap<>();
static {
MAP.put('N', new int[]{0, 1});
MAP.put('S', new int[]{0, -1});
MAP.put('E', new int[]{1, 0});
MAP.put('W', new int[]{-1, 0});
}
public int maxDistance(String s, int k) {
int res = 0;
int d = 0;
int prev = 0;
int backCnt = 0;
int[] curPos = new int[]{0, 0};
char[] move = s.toCharArray();
for (char dir : move) {
prev = d;
int[] delta = MAP.get(dir);
int dx = delta[0];
int dy = delta[1];
curPos[0] += dx;
curPos[1] += dy;
d = Math.abs(curPos[0]) + Math.abs(curPos[1]);
if (prev > d) {
backCnt++;
}
res = Math.max(res, d + Math.min(backCnt, k) * 2);
}
return res;
}
}
性能
