目标
给你一个字符串 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
思路
有一个长度为偶数 n 的字符串，有 n / 2 个 [ 和 ]。定义括号能够匹配的字符串是平衡字符串。每一次操作可以交换任意两个下标对应的括号，求将字符串变平衡的最少操作次数。
[[]] 和 [][] 都是平衡字符串，如何确定该与哪个括号交换才能使操作次数最小？对于 ]][[ 和 ][][，第一个与最后一个交换之后变为平衡字符串 [][] 和 [[]]。而如果选择与倒数第二个 [ 交换，会变成 []][，需要再交换一次才能变为平衡字符串。
平衡字符串有这样的性质：其前缀中 [ 的个数总是大于等于 ] 的个数。如果发现 ] 的个数超过 [，那么必须要进行交换。最好将它交换到最后，因为这样可以减少它在前面前缀中对 ] 的贡献，将交换操作尽可能地延后，减小必须进行交换的次数。
也可以先将平衡的括号消掉，剩下的必然是 ]]]......[[[ 的形式。交换一次最多可以抵消 4 个，最少抵消 2 个，即 (stack.size() + 2) / 4。
代码
/**
* @date 2025-03-17 16:32
*/
public class MinSwaps1963 {
public int minSwaps_v1(String s) {
int n = s.length();
int left = 0, right = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '[') {
left++;
} else if (c == ']' && left > 0) {
left--;
} else {
right++;
}
}
return (left + right + 2) / 4;
}
public int minSwaps(String s) {
int n = s.length();
ArrayDeque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
stack.push(c);
}
}
return (stack.size() + 2) / 4;
}
}
性能
