从Leetcode 每日一题练习继续讨论：
1963. 使字符串平衡的最小交换次数
1963. Minimum Number of Swaps to Make the String Balanced
题解
本题也是一道括号匹配问题，题面为通过调换顺序让字符串中所有中括号都是匹配的。本题明确说明左括号和右括号的数量相同，即最终一定可以全部匹配。括号匹配问题离不开栈结构，对于左括号直接入栈，遇到右括号且同时栈顶为左括号则匹配成功，将栈顶左括号出栈。若栈中没有可供匹配的左括号，遇到右括号则将右括号当作左括号入栈同时将“调换”变量+1。继续正常匹配括号，直到字符串剩余未匹配长度和当前被“调换”的字符个数相同为止，被调换的字符个数即为最小交换次数。
这种情况下，可以发现栈中永远只存在左括号，因此只需记录当前栈中左括号的个数就足够了，无需真的将左括号放入栈中。
贪心完全是看题目后的直觉，隐约感觉这样解可能就是对的，再用题目示例验证一下发现确实能得到正确结果，但是不能光靠感觉解题，还是需要证明贪心的正确性。为什么贪心算法就能得到最优解呢。原因在于每次我们将出现不平衡位置的右括号与后面的左括号交换时，可以使交换的两个括号都能与某个对应括号匹配上，若后面的左括号本来是不匹配的，交换位置后一定可以匹配，因为至少还可以与被交换的右括号匹配，而对右括号同理。若本来是匹配的，则交换后其仍然是匹配的，也就是说至少不会更差，考虑右括号一定从不匹配变成匹配，则这种交换已经是局部最优选择，本题因为左右括号数量相同，最终一定可以全部匹配，则不断的局部最优最终可以得到全局最优。
代码
class Solution {
public:
int minSwaps(string s) {
int result = 0;
int length = s.size();
int stacklen = 0;
for (int i=0;i<s.size();i++){
if ((length-i-1) == result){
break;
}
if (s[i] == '['){
stacklen++;
}else if (s[i] == ']'){
if (stacklen > 0){
stacklen--;
}else{
stacklen++;
result++;
}
}
}
return result;
}
};