3443. K次改变后的最大曼哈顿距离

Medium

题目描述

给你一个由字符 ‘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"。
最大曼哈顿距离为 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’ 组成。

解题思路

这是一个动态规划问题，关键在于理解曼哈顿距离的性质和最优策略。

核心思路：

曼哈顿距离 |x| + |y| 在某个时刻最大，意味着我们要让坐标尽可能远离原点
最优策略是朝着某个特定方向移动，可以是四个主要方向：东北(NE)、西北(NW)、东南(SE)、西南(SW)
对于每个方向，我们需要计算在该方向上能达到的最大距离

算法步骤：

枚举四个可能的最优方向组合：(N,E)、(N,W)、(S,E)、(S,W)
对于每个方向组合，使用贪心策略：优先改变那些与目标方向相反的字符
在每一步移动中，计算当前位置的曼哈顿距离，并更新最大值
使用动态规划来高效计算在每个位置使用不同修改次数能达到的最大距离

时间复杂度优化： 我们可以预处理每个方向的贡献，然后对于每个可能的方向组合，计算在限制 k 次修改下能达到的最大距离。关键是要在模拟移动过程中实时跟踪最大曼哈顿距离。

代码实现

class Solution {
public:
    int maxDistance(string s, int k) {
        int n = s.length();
        int result = 0;
        
        // 四个可能的方向组合: (dx, dy) 对应 (x方向优先字符, y方向优先字符)
        vector<pair<char, char>> directions = {{'N', 'E'}, {'N', 'W'}, {'S', 'E'}, {'S', 'W'}};
        
        for (auto& dir : directions) {
            char target_x = dir.first;
            char target_y = dir.second;
            
            // 计算每个位置改变为目标方向的收益
            vector<int> benefit(n);
            for (int i = 0; i < n; i++) {
                if (s[i] == target_x || s[i] == target_y) {
                    benefit[i] = 0;  // 已经是目标方向
                } else if ((s[i] == 'N' && target_x == 'S') || (s[i] == 'S' && target_x == 'N') ||
                          (s[i] == 'E' && target_y == 'W') || (s[i] == 'W' && target_y == 'E')) {
                    benefit[i] = 2;  // 相反方向，收益为2
                } else {
                    benefit[i] = 1;  // 垂直方向，收益为1
                }
            }
            
            // 使用优先队列贪心选择修改
            vector<pair<int, int>> changes;  // (benefit, index)
            for (int i = 0; i < n; i++) {
                if (benefit[i] > 0) {
                    changes.push_back({benefit[i], i});
                }
            }
            sort(changes.rbegin(), changes.rend());
            
            // 应用最多k个修改
            string modified = s;
            int used = 0;
            for (auto& change : changes) {
                if (used >= k) break;
                int idx = change.second;
                // 决定改为哪个方向
                if (s[idx] == 'N' || s[idx] == 'S') {
                    modified[idx] = target_y;
                } else {
                    modified[idx] = target_x;
                }
                used++;
            }
            
            // 模拟移动并计算最大曼哈顿距离
            int x = 0, y = 0;
            for (char c : modified) {
                if (c == 'N') y++;
                else if (c == 'S') y--;
                else if (c == 'E') x++;
                else if (c == 'W') x--;
                
                result = max(result, abs(x) + abs(y));
            }
        }
        
        return result;
    }
};

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        n = len(s)
        result = 0
        
        # 四个可能的方向组合
        directions = [('N', 'E'), ('N', 'W'), ('S', 'E'), ('S', 'W')]
        
        for target_x, target_y in directions:
            # 计算每个位置改变为目标方向的收益
            benefit = []
            for i, c in enumerate(s):
                if c == target_x or c == target_y:
                    benefit.append((0, i))  # 已经是目标方向
                elif (c == 'N' and target_x == 'S') or (c == 'S' and target_x == 'N') or \
                     (c == 'E' and target_y == 'W') or (c == 'W' and target_y == 'E'):
                    benefit.append((2, i))  # 相反方向，收益为2
                else:
                    benefit.append((1, i))  # 垂直方向，收益为1
            
            # 按收益排序，贪心选择修改
            benefit.sort(reverse=True)
            
            # 应用最多k个修改
            modified = list(s)
            used = 0
            for b, idx in benefit:
                if used >= k or b == 0:
                    break
                # 决定改为哪个方向
                if s[idx] in 'NS':
                    modified[idx] = target_y
                else:
                    modified[idx] = target_x
                used += 1
            
            # 模拟移动并计算最大曼哈顿距离
            x, y = 0, 0
            for c in modified:
                if c == 'N':
                    y += 1
                elif c == 'S':
                    y -= 1
                elif c == 'E':
                    x += 1
                elif c == 'W':
                    x -= 1
                
                result = max(result, abs(x) + abs(y))
        
        return result

public class Solution {
    public int MaxDistance(string s, int k) {
        int n = s.Length;
        int result = 0;
        
        // 四个可能的方向组合
        char[,] directions = {{'N', 'E'}, {'N', 'W'}, {'S', 'E'}, {'S', 'W'}};
        
        for (int d = 0; d < 4; d++) {
            char targetX = directions[d, 0];
            char targetY = directions[d, 1];
            
            // 计算每个位置改变为目标方向的收益
            var benefit = new List<(int benefit, int index)>();
            for (int i = 0; i < n; i++) {
                char c = s[i];
                if (c == targetX || c == targetY) {
                    benefit.Add((0, i));  // 已经是目标方向
                } else if ((c == 'N' && targetX == 'S') || (c == 'S' && targetX == 'N') ||
                          (c == 'E' && targetY == 'W') || (c == 'W' && targetY == 'E')) {
                    benefit.Add((2, i));  // 相反方向，收益为2
                } else {
                    benefit.Add((1, i));  // 垂直方向，收益为1
                }
            }
            
            // 按收益排序，贪心选择修改
            benefit.Sort((a, b) => b.benefit.CompareTo(a.benefit));
            
            // 应用最多k个修改
            char[] modified = s.ToCharArray();
            int used = 0;
            foreach (var (b, idx) in benefit) {
                if (used >= k || b == 0) break;
                // 决定改为哪个方向
                if (s[idx] == 'N' || s[idx] == 'S') {
                    modified[idx] = targetY;
                } else {
                    modified[idx] = targetX;
                }
                used++;
            }
            
            // 模拟移动并计算最大曼哈顿距离
            int x = 0, y = 0;
            foreach (char c in modified) {
                if (c == 'N') y++;
                else if (c == 'S') y--;
                else if (c == 'E') x++;
                else if (c == 'W') x--;
                
                result = Math.Max(result, Math.Abs(x) + Math.Abs(y));
            }
        }
        
        return result;
    }
}

var maxDistance = function(s, k) {
    const n = s.length;
    let maxDist = 0;
    
    // Try all possible ways to distribute k changes between x and y axes
    for (let kx = 0; kx <= k; kx++) {
        const ky = k - kx;
        
        // Calculate max distance for this distribution
        let x = 0, y = 0;
        let tempMaxDist = 0;
        
        // Arrays to store net movements at each step
        const xMoves = [];
        const yMoves = [];
        
        // Calculate movements without changes first
        for (let i = 0; i < n; i++) {
            if (s[i] === 'E') xMoves.push(1);
            else if (s[i] === 'W') xMoves.push(-1);
            else xMoves.push(0);
            
            if (s[i] === 'N') yMoves.push(1);
            else if (s[i] === 'S') yMoves.push(-1);
            else yMoves.push(0);
        }
        
        // Try to optimize x-axis movements with kx changes
        const xDeltas = [];
        for (let i = 0; i < n; i++) {
            let currentX = 0;
            for (let j = 0; j <= i; j++) {
                currentX += xMoves[j];
            }
            
            // Calculate benefit of changing each previous move
            let maxBenefit = 0;
            const benefits = [];
            
            for (let j = 0; j <= i; j++) {
                let benefit = 0;
                if (currentX >= 0) {
                    // Want to maximize |x|, so prefer moves in same direction
                    benefit = 2 - xMoves[j] * (currentX >= 0 ? 1 : -1);
                    if (xMoves[j] === 0) benefit = 1;
                    else if (xMoves[j] * (currentX >= 0 ? 1 : -1) < 0) benefit = 2;
                    else benefit = 0;
                } else {
                    if (xMoves[j] === 0) benefit = 1;
                    else if (xMoves[j] * (currentX >= 0 ? 1 : -1) < 0) benefit = 2;
                    else benefit = 0;
                }
                benefits.push(benefit);
            }
            
            benefits.sort((a, b) => b - a);
            let optimalX = currentX;
            for (let c = 0; c < Math.min(kx, benefits.length); c++) {
                if (benefits[c] > 0) {
                    if (optimalX >= 0) optimalX += benefits[c];
                    else optimalX -= benefits[c];
                }
            }
            xDeltas.push(Math.abs(optimalX));
        }
        
        // Try to optimize y-axis movements with ky changes
        const yDeltas = [];
        for (let i = 0; i < n; i++) {
            let currentY = 0;
            for (let j = 0; j <= i; j++) {
                currentY += yMoves[j];
            }
            
            let maxBenefit = 0;
            const benefits = [];
            
            for (let j = 0; j <= i; j++) {
                let benefit = 0;
                if (yMoves[j] === 0) benefit = 1;
                else if (yMoves[j] * (currentY >= 0 ? 1 : -1) < 0) benefit = 2;
                else benefit = 0;
                benefits.push(benefit);
            }
            
            benefits.sort((a, b) => b - a);
            let optimalY = currentY;
            for (let c = 0; c < Math.min(ky, benefits.length); c++) {
                if (benefits[c] > 0) {
                    if (optimalY >= 0) optimalY += benefits[c];
                    else optimalY -= benefits[c];
                }
            }
            yDeltas.push(Math.abs(optimalY));
        }
        
        // Find maximum Manhattan distance for this k distribution
        for (let i = 0; i < n; i++) {
            tempMaxDist = Math.max(tempMaxDist, xDeltas[i] + yDeltas[i]);
        }
        
        maxDist = Math.max(maxDist, tempMaxDist);
    }
    
    return maxDist;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n log n)
空间复杂度	O(n)

其中 n 是字符串的长度。时间复杂度主要来自于对每个方向组合的排序操作，空间复杂度来自于存储收益数组和修改后的字符串。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目