LeetCode 3443: Maximum Manhattan Distance After K Changes (Greedy / Prefix)
English
For each prefix of moves, let base distance be |E-W| + |N-S|. One change can increase Manhattan distance by at most 2, so best distance for this prefix is min(prefixLen, base + 2k). Scan all prefixes and keep the maximum.
class Solution {
public int maxDistance(String s, int k) {
int n = s.length(), e = 0, w = 0, nn = 0, ss = 0, ans = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == 'E') e++;
else if (c == 'W') w++;
else if (c == 'N') nn++;
else ss++;
int base = Math.abs(e - w) + Math.abs(nn - ss);
int best = Math.min(i + 1, base + 2 * k);
ans = Math.max(ans, best);
}
return ans;
}
}func maxDistance(s string, k int) int {
e, w, n, ss, ans := 0, 0, 0, 0, 0
for i, c := range s {
if c == 'E' {
e++
} else if c == 'W' {
w++
} else if c == 'N' {
n++
} else {
ss++
}
base := abs(e-w) + abs(n-ss)
best := min(i+1, base+2*k)
ans = max(ans, best)
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a,b int) int { if a<b {return a}; return b }
func max(a,b int) int { if a>b {return a}; return b }class Solution {
public:
int maxDistance(string s, int k) {
int e=0,w=0,n=0,ss=0,ans=0;
for (int i=0;i<(int)s.size();i++) {
if (s[i]=='E') e++;
else if (s[i]=='W') w++;
else if (s[i]=='N') n++;
else ss++;
int base=abs(e-w)+abs(n-ss);
int best=min(i+1, base+2*k);
ans=max(ans,best);
}
return ans;
}
};class Solution:
def maxDistance(self, s: str, k: int) -> int:
e = w = n = ss = ans = 0
for i, c in enumerate(s):
if c == 'E':
e += 1
elif c == 'W':
w += 1
elif c == 'N':
n += 1
else:
ss += 1
base = abs(e - w) + abs(n - ss)
best = min(i + 1, base + 2 * k)
ans = max(ans, best)
return ansvar maxDistance = function(s, k) {
let e = 0, w = 0, n = 0, ss = 0, ans = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === 'E') e++;
else if (c === 'W') w++;
else if (c === 'N') n++;
else ss++;
const base = Math.abs(e - w) + Math.abs(n - ss);
const best = Math.min(i + 1, base + 2 * k);
ans = Math.max(ans, best);
}
return ans;
};中文
按前缀扫描。设当前前缀原始曼哈顿距离为 |E-W| + |N-S|。一次修改最多让距离增加 2，因此该前缀可达到的最优值是 min(前缀长度, base + 2k)。对所有前缀取最大值即可。
class Solution {
public int maxDistance(String s, int k) {
int n = s.length(), e = 0, w = 0, nn = 0, ss = 0, ans = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == 'E') e++;
else if (c == 'W') w++;
else if (c == 'N') nn++;
else ss++;
int base = Math.abs(e - w) + Math.abs(nn - ss);
int best = Math.min(i + 1, base + 2 * k);
ans = Math.max(ans, best);
}
return ans;
}
}func maxDistance(s string, k int) int {
e, w, n, ss, ans := 0, 0, 0, 0, 0
for i, c := range s {
if c == 'E' {
e++
} else if c == 'W' {
w++
} else if c == 'N' {
n++
} else {
ss++
}
base := abs(e-w) + abs(n-ss)
best := min(i+1, base+2*k)
ans = max(ans, best)
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a,b int) int { if a<b {return a}; return b }
func max(a,b int) int { if a>b {return a}; return b }class Solution {
public:
int maxDistance(string s, int k) {
int e=0,w=0,n=0,ss=0,ans=0;
for (int i=0;i<(int)s.size();i++) {
if (s[i]=='E') e++;
else if (s[i]=='W') w++;
else if (s[i]=='N') n++;
else ss++;
int base=abs(e-w)+abs(n-ss);
int best=min(i+1, base+2*k);
ans=max(ans,best);
}
return ans;
}
};class Solution:
def maxDistance(self, s: str, k: int) -> int:
e = w = n = ss = ans = 0
for i, c in enumerate(s):
if c == 'E':
e += 1
elif c == 'W':
w += 1
elif c == 'N':
n += 1
else:
ss += 1
base = abs(e - w) + abs(n - ss)
best = min(i + 1, base + 2 * k)
ans = max(ans, best)
return ansvar maxDistance = function(s, k) {
let e = 0, w = 0, n = 0, ss = 0, ans = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === 'E') e++;
else if (c === 'W') w++;
else if (c === 'N') n++;
else ss++;
const base = Math.abs(e - w) + Math.abs(n - ss);
const best = Math.min(i + 1, base + 2 * k);
ans = Math.max(ans, best);
}
return ans;
};