• 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, 0
        for d in s:
            dx, dy = direction[d]
            x, y = x+dx, y+dy
            cnt[d] += 1
            ans = 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。