Solutions CS101

Appearance

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

stack, greedy, https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced/

给你一个字符串 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
python
class Solution:
    def minSwaps(self, s: str) -> int:
        """
        计算将字符串 s 变成平衡字符串所需的最小交换次数。
        
        算法思路：
        1. 使用变量 balance 表示当前的平衡度：遇到 '[' 增加 1，遇到 ']' 减少 1。
        2. 当 balance 小于 0 时，说明右括号太多，需要进行一次交换：
        - 交换后，相当于把一个 '[' 移动到当前不平衡的位置，
        - 同时将 balance 增加 2（因为原本是 -1，变成 +1）。
        3. 累加交换次数，最后返回总交换次数。
        
        时间复杂度：O(n)
        """
        balance = 0  # 当前字符串的平衡度
        swaps = 0    # 需要的最小交换次数

        for char in s:
            if char == '[':
                balance += 1
            else:  # char == ']'
                balance -= 1

            # 如果 balance 小于 0，说明右括号数量多于左括号，需要交换
            if balance < 0:
                swaps += 1
                balance += 2  # 交换后，相当于把一个 '[' 带到当前位置

        return swaps

很多时候题目标签只是提示可能的思路，而最终能AC的代码可能只用了一种更简单的写法。比如说：

  • 平衡变量法：用一个 balance 变量，遇到 '[' 加 1，遇到 ']' 减 1。当 balance 变负时就说明当前位置不平衡，需要做一次交换，并将 balance 加 2。这个过程本质上隐含了栈的匹配思想（只不过不用真的维护一个栈）和贪心的“遇到不平衡就立即修正”的思想。至于双指针，有的解法会显式寻找交换的左右位置，但实际上我们只关心交换次数，而不用真地模拟每一步的交换。

因此，虽然代码里没有显式地写出栈、双指针等数据结构，但它们的思想都内含在对 balance 的更新过程中。

所以，用 balance 的方法既简单又高效，完全可以AC，而不一定需要额外的栈或者双指针的显式操作。