Medium

题目描述

给你一个长度为 n 的字符串 s，下标从 0 开始。字符串由 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

解题思路

解题思路

这道题的核心是理解什么情况下需要交换，以及每次交换能解决多少不平衡。

方法一：贪心算法（推荐）

关键观察：

  1. 由于开括号和闭括号数量相等，最终一定能达到平衡
  2. 从左到右遍历时，如果某个位置闭括号数量超过了开括号，就产生了"不匹配"
  3. 每次交换一个多余的闭括号和后面的开括号，可以减少2个不匹配

具体步骤：

  • 用 balance 记录当前的平衡状态（开括号+1，闭括号-1）
  • 当 balance < 0 时，说明闭括号过多，记录最小值
  • 最少交换次数 = (|最小balance值| + 1) / 2

方法二：栈模拟

使用栈来模拟括号匹配过程，统计无法匹配的闭括号数量，交换次数为 (不匹配数 + 1) / 2。

两种方法时间复杂度相同，但贪心算法空间复杂度更优。

代码实现

class Solution {
public:
    int minSwaps(string s) {
        int balance = 0;
        int minBalance = 0;
        
        for (char c : s) {
            if (c == '[') {
                balance++;
            } else {
                balance--;
            }
            minBalance = min(minBalance, balance);
        }
        
        return (-minBalance + 1) / 2;
    }
};

class Solution:
    def minSwaps(self, s: str) -> int:
        balance = 0
        min_balance = 0
        
        for c in s:
            if c == '[':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        
        return (-min_balance + 1) // 2

public class Solution {
    public int MinSwaps(string s) {
        int balance = 0;
        int minBalance = 0;
        
        foreach (char c in s) {
            if (c == '[') {
                balance++;
            } else {
                balance--;
            }
            minBalance = Math.Min(minBalance, balance);
        }
        
        return (-minBalance + 1) / 2;
    }
}

var minSwaps = function(s) {
    let balance = 0;
    let minBalance = 0;
    
    for (let char of s) {
        if (char === '[') {
            balance++;
        } else {
            balance--;
        }
        minBalance = Math.min(minBalance, balance);
    }
    
    return Math.ceil(-minBalance / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。只需要一次遍历，使用常数额外空间。

相关题目