1963. 使字符串平衡的最小交换次数 - 力扣（LeetCode）
给你一个字符串 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.length2 <= n <= 106n为偶数s[i]为'['或']'- 开括号
'['的数目为n / 2，闭括号']'的数目也是n / 2
这道题是一道显然的贪心。我一开始就想到可能要用双指针，左指针每次选出第一个无法被匹配的右括号，然后去和右边开始数第一个无法被匹配的左括号（也就是右指针干的事）交换位置。但不知道这样做是否是正确的，仅仅只是题感告诉我要这样做。后来发现，这样做确实是对的，事实上甚至可以不需要右指针去选出第一个无法匹配的左括号，仅仅需要用从右开始的第一个左括号来进行交换即可。
我们考察平衡字符串的性质。
在平衡字符串的任意一个前缀中，左括号的数量都大于等于右括号的数量。例如平衡字符串 "[[]][]"，它的前缀有 "[[]"，"[[]][" 等，都满足这一性质。为什么？因为对于前缀来说，每个右括号的左边，必然有与之匹配的左括号，但左括号不一定有与之匹配的右括号。
根据这一性质，从左到右遍历字符串 s，统计未匹配的左括号的个数 c：遇到左括号就把 c 加一，遇到右括号就把 c 减一。如果任何时刻 c 都不为负数，那么 s 就是平衡字符串。（注意题目保证左右括号个数相等，所以最终 c 一定为 0。）
反之，如果遍历到右括号，且此时 c=0，那么减一后 c 是负数，说明右括号比左括号多，必然存在一个右括号，没有相匹配的左括号，无论后面的字符是什么样的，s 都不可能是平衡字符串。例如 s="[]]["。
这时就需要把这个右括号换走了。和另一个右括号交换是没有意义的（s 不变），所以一定要和左括号交换。
右上，其实我们就可以知道，我在一开始所述的那种方式一定是最优的，因为对于交换两个括号位置而言，没有比这样的交换方式更优的，更能接近答案的方案了。
class Solution {
public:
int minSwaps(string s) {
int ans = 0, c = 0;
int d = 0;
int j = s.size() - 1;
for (char b : s)
{
if (b == '[')
{
c++;
}
else if (c > 0)
{
c--;
}
else
{ // c == 0
// 找最右边的左括号交换
while (true) //关于左右指针相交，即右指针小于左指针的判断是不需要的
//因为根据题意，当需要右指针移动时，左指针的右边不可能不存在一个无法被匹配的左括号，那么右指针此时的值也一定会小于等于该左括号的位置。
{
if(s[j] == ']')
d++;
else if(d>0)
d--;
else
{
break;
}
j--;
}
s[j] = ']'; // s[i] = '[' 可以省略
ans++;
c++; // s[i] 变成左括号，c 加一
}
}
return ans;
}
};