Leetcode 3443. Maximum Manhattan Distance After K Changes

• Leetcode 3443. Maximum Manhattan Distance After K Changes
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3443. Maximum Manhattan Distance After K Changes

1. 解题思路

这一题思路上算是一个类似滑动窗口的思路，核心思想就是在每一步走到的位置上考虑如何通过至多$k$次调整使得其位置推到最远。

具体实现来说，就是考察任意时刻下目标所在的位置，然后考虑将其沿着其所在的象限如何推至最远，比如在第一象限，那就将所有历史中往南以及往西的move进行调整，使之同样往北或者往东，这样就可以产生至多$2k$的距离增量，然后我们遍历所有的时刻，返回其最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:def maxDistance(self, s: str, k: int) -> int:direction = {"N": [0, 1], "S": [0, -1], "E": [1, 0], "W": [-1, 0]}cnt = defaultdict(int)x, y, ans = 0, 0, 0for d in s:dx, dy = direction[d]x, y = x+dx, y+dycnt[d] += 1ans = max(ans, abs(x) + abs(y))if y >= 0 and x >= 0:if cnt["S"] + cnt["W"] >= k:ans = max(ans, abs(x) + abs(y) + 2*k)else:ans = max(ans, abs(x) + abs(y) + 2*(cnt["S"] + cnt["W"]))elif y >= 0 and x <= 0:if cnt["S"] + cnt["E"] >= k:ans = max(ans, abs(x) + abs(y) + 2*k)else:ans = max(ans, abs(x) + abs(y) + 2*(cnt["S"] + cnt["E"]))elif y <= 0 and x >= 0:if cnt["N"] + cnt["W"] >= k:ans = max(ans, abs(x) + abs(y) + 2*k)else:ans = max(ans, abs(x) + abs(y) + 2*(cnt["N"] + cnt["W"]))else:if cnt["N"] + cnt["E"] >= k:ans = max(ans, abs(x) + abs(y) + 2*k)else:ans = max(ans, abs(x) + abs(y) + 2*(cnt["N"] + cnt["E"]))return ans

提交代码评测得到：耗时2310ms，占用内存18.1MB。