本文涉及知识点

C++栈

LeetCode1963. 使字符串平衡的最小交换次数

给你一个字符串 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⁶
  n 为偶数
  s[i] 为’[’ 或 ‘]’
  开括号 ‘[’ 的数目为 n / 2 ，闭括号 ‘]’ 的数目也是 n / 2

C++栈

左括号权值1，右括号-1。
p[i] = s[0…i]的权值和。
合法括号$⟺$
条件一，$\forall$i,p[i]>=0。
条件二，p.back()等于0。本题左右括号相等，故一定成立。
i从小到大处理p[i]，如果p[i] < 0，则说明s[i]是右括号，和s[i…]的左括号交换，和s[0…i-1]交换不影响p[i]。
i < x1 < x2 ，s[x1]、s[x2]都是[。和x2交换相比和x1交换,p[x1…x2-1]大1，这显然有利于条件一。故选择x2。
用栈记录]的下标，如果需要交换，和栈顶的下标交换，并出栈。

代码

核心代码

class Solution {
		public:
			int minSwaps(string s) {
				stack<int> indexs;
				for (int i = 0; i < s.length(); i++) {
					if ('[' == s[i]) {
						indexs.emplace(i);
					}
				}
				int cur = 0;
				int ret = 0;
				for (int i = 0; i < s.length(); i++) {
					if ('[' == s[i]) {
						cur++;
					}
					else {
						if (0 == cur) {
							swap(s[i], s[indexs.top()]);
							indexs.pop();
							cur = 1;
							ret++;
						}
						else {
							cur--;
						}
					}
				}
				return ret;
			}
		};

单元测试

	string s;
		TEST_METHOD(TestMethod11)
		{
			s = "][][";
			auto res = Solution().minSwaps(s);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "]]][[[";
			auto res = Solution().minSwaps(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "[]";
			auto res = Solution().minSwaps(s);
			AssertEx(0, res);
		}