[LeetCode] 每日一题 1963. 使字符串平衡的最小交换次数
题目链接
题目描述
给你一个字符串 s
,下标从 0 开始 ,且长度为偶数 n
。字符串 恰好 由 n / 2
个开括号 '['
和 n / 2
个闭括号 ']'
组成。
只有能满足下述所有条件的字符串才能称为 平衡字符串 :
字符串是一个空字符串,或者
字符串可以记作
AB
,其中A
和B
都是 平衡字符串 ,或者字符串可以写成
[C]
,其中C
是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。
返回使 s
变成 平衡字符串 所需要的 最小 交换次数。
示例输入
示例 1
输入:s = "][]["
输出:1
解释:交换下标 0 和下标 3 对应的括号,可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。
示例 2
输入:s = "]]][[["
输出:2
解释:执行下述操作可以使字符串变成平衡字符串:
- 交换下标 0 和下标 4 对应的括号,s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号,s = "[[][]]" 。
最终字符串变成 "[[][]]" 。
示例 3
输入:s = "[]"
输出:0
解释:这个字符串已经是平衡字符串。
提示
n == s.length
2 <= n <= 10^6
n
为偶数s[i]
为'['
或']'
开括号
'['
的数目为n / 2
,闭括号']'
的数目也是n / 2
解题思路
本题要求通过最小交换次数将字符串变为平衡字符串。由于交换可以发生在任意两个位置,我们可以贪心地尽量让右括号 ]
及时匹配到左括号 [
,从而减少后续的交换次数
我们使用一个 cnt
变量来记录当前未匹配的左括号 [
数量:
遍历字符串时,遇到
[
,cnt
加一,表示新增一个未匹配的左括号遇到
]
时,如果cnt > 0
,说明可以匹配[
,因此cnt
减一如果
cnt == 0
但仍然遇到了]
,说明此时]
需要通过交换来匹配一个[
,因此我们将ans
(交换次数)加一,并假设执行交换后cnt
继续保持正数,以匹配后续的括号
最终,ans
即为最小交换次数
代码实现
class Solution {
public int minSwaps(String s) {
int cnt = 0;
int ans = 0;
for (char c : s.toCharArray()) {
if (c == '[') {
cnt++;
} else if (cnt > 0) {
cnt--;
} else {
ans++;
cnt++;
}
}
return ans;
}
}
复杂度分析
时间复杂度:O(n),遍历字符串一次即可完成计算
空间复杂度:O(1),只使用了两个额外的整数变量
cnt
和ans
,不会额外占用空间
总结
本题利用贪心算法,通过计数未匹配的左括号数量,确保右括号 ]
尽早匹配,从而最小化交换次数。核心思想是当 ]
无法匹配时,执行交换,使 ]
能够匹配一个 [
。这是一种典型的局部最优 -> 全局最优的贪心策略
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。