好的，我们来看一个不在你历史列表中的线性动态规划题目。

最少操作使字符串平衡（Minimum Swaps to Make Strings Balanced）

题目描述

给你一个只包含字符 '[' 和 ']' 的字符串 s，长度是 n。字符串 s 是 不平衡 的。

你可以执行一种操作：

• 选择字符串中任意两个索引 i 和 j（其中 i 和 j 可以相邻，也可以不相邻），然后交换 s[i] 和 s[j]。

你的目标是：通过 最少 的交换次数，使字符串变成一个 平衡 的字符串。

平衡字符串的定义：

1. 空字符串 "" 是平衡的。
2. 如果字符串 A 和 B 都是平衡的，那么字符串 AB 也是平衡的。
3. 如果字符串 S 是平衡的，那么字符串 "[" + S + "]" 也是平衡的。

换句话说，一个平衡字符串是合法的括号字符串，其中所有括号都能正确匹配。

示例 1：
输入：s = "][]["
输出：1
解释：将 s[0] 和 s[2] 交换，得到 "[]]["，字符串仍然不平衡。但将 s[0] 和 s[3] 交换，得到 "[][]"，这是平衡的。所以最少需要 1 次交换。

示例 2：
输入：s = "]]][[["
输出：2
解释：一种可能方案是：先交换 s[0] 和 s[5] 得到 "[]][]["，再交换 s[2] 和 s[3] 得到 "[][][]"。

约束：

• n == s.length
• 1 <= n <= 10^5
• s[i] 要么是 '['，要么是 ']'。

题目分析

首先，一个字符串要成为合法括号字符串，其 '[' 和 ']' 的数量必须相等。题目虽然没明说，但输入字符串的长度 n 是偶数，并且 '[' 和 ']' 的数量通常相等（如果不相等，则不可能通过交换变成平衡，但题目隐含了可以做到的条件）。

核心问题在于括号的相对位置不对。我们需要通过交换，让所有的 '[' 出现在其匹配的 ']' 之前。

第一步：理解不匹配的本质

我们如何衡量一个字符串的不平衡程度？
一个经典的方法是使用一个 计数器（通常叫做 balance）：

• 遍历字符串，遇到 '[' 就加 1，遇到 ']' 就减 1。
• 这个 balance 的值代表了当前未匹配的左括号数量。

对于一个平衡字符串，在整个遍历过程中，balance 始终 >= 0，并且在遍历结束时 balance = 0。

如果某个时刻 balance 变成了 负数，就说明当前遇到了一个多余的右括号 ']'，它前面没有足够的左括号来匹配它。这就是一个 需要被纠正 的错误位置。

例子：
s = "]]][[["
遍历：

• i=0: ']' -> balance = -1 (负了！)
• i=1: ']' -> balance = -2 (负了！)
• i=2: ']' -> balance = -3 (负了！)
• i=3: '[' -> balance = -2
• i=4: '[' -> balance = -1
• i=5: '[' -> balance = 0

我们看到 balance 有三次变成负数。这三次就对应了三个“非法的”右括号。

第二步：从不匹配到交换策略

我们注意到，每当我们遇到 balance 变成负数时，就说明我们遇到了一个位置 j，它前面右括号太多，左括号太少。

怎么修复呢？
我们需要 从后面找一个 '[' 和这个位置（或者某个代表位置）的 ']' 进行交换。这样，就能把一个左括号提前，增加前面的 balance 值，避免它变成负数。

这个“从后面找 '['”的想法是贪心的：为了修复当前这个负数危机，我们找任何一个后面的 '[' 都行，并且越早交换，收益越大。

更具体地说：
我们用 cnt 来记录遍历过程中 balance 首次变成负数 的情况。
但更简单的是，我们用一个变量 imbalance 来记录 balance 达到的 历史最小值（因为是最小值，所以是负数或0）。

关键观察：

• 这个 历史最小值 imbalance 的绝对值，代表了在最坏的前缀中，我们“欠”了多少个左括号。例如，上面例子中 imbalance = -3。
• 为了修正这个最坏的情况，我们需要至少引入 ceil(abs(imbalance) / 2) 个左括号到前面来。
  为什么除以2？因为一次交换可以解决两个问题：
  1. 把一个多余的 ']' 换到后面去（它去后面可能是合适的）。
  2. 把一个需要的 '[' 换到前面来（增加前面的 balance）。
     一次交换正好能“抵消”两个单位的 imbalance（把 balance 从 -k 提升到 -k+2）。

第三步：动态规划思想的运用（线性DP）

虽然这个问题的核心解法很简洁，但它体现了线性动态规划中一种重要的思想：用状态变量（这里是 balance）来累积历史信息，并根据当前决策（遇到 '[' 或 ']'）更新状态，最终从状态中推导出答案。

我们定义：

• balance：遍历到当前位置时，未匹配的左括号数量（可以理解为当前前缀的净匹配度）。
• max_imbalance：balance 在遍历过程中达到的最小值（因为是负数，所以用“最大不平衡度”可能指绝对值，但这里我们直接记录最小值）。

状态转移：
初始化 balance = 0, max_imbalance = 0。
遍历字符串 s 的每个字符 c：

• 如果 c == '[': balance = balance + 1
• 如果 c == ']': balance = balance - 1
• 更新 max_imbalance = min(max_imbalance, balance)

遍历结束后，balance 一定为 0（因为左右括号数量相等）。

最终答案：
ans = ceil(abs(max_imbalance) / 2)，其中 ceil 表示向上取整。

向上取整的原因：如果最差的时候欠了奇数个左括号，比如 max_imbalance = -3，我们需要 2 次交换（因为一次交换提升 balance 2点，-3 -> -1 -> 1 需要两次）。公式 (abs(imbalance) + 1) / 2 可以等价实现向上取整（在整数除法中）。

第四步：验证公式与例子

例子 1： s = "][]["
遍历：

• i=0: ']' -> balance = -1, max_imbalance = -1
• i=1: '[' -> balance = 0, max_imbalance = -1
• i=2: ']' -> balance = -1, max_imbalance = -1
• i=3: '[' -> balance = 0, max_imbalance = -1
  max_imbalance = -1
ans = (1 + 1) / 2 = 1 ✔

例子 2： s = "]]][[["
遍历：

• i=0: ']' -> balance = -1, max_imbalance = -1
• i=1: ']' -> balance = -2, max_imbalance = -2
• i=2: ']' -> balance = -3, max_imbalance = -3
• i=3: '[' -> balance = -2, max_imbalance = -3
• i=4: '[' -> balance = -1, max_imbalance = -3
• i=5: '[' -> balance = 0, max_imbalance = -3
  max_imbalance = -3
ans = (3 + 1) / 2 = 2 ✔

第五步：算法实现与复杂度

def minSwaps(s: str) -> int:
    balance = 0
    max_imbalance = 0  # 记录balance的历史最小值（负数或0）
    
    for ch in s:
        if ch == '[':
            balance += 1
        else:  # ch == ']'
            balance -= 1
        # 更新历史最小值
        max_imbalance = min(max_imbalance, balance)
    
    # max_imbalance 是负数或0，我们需要其绝对值
    imbalance = -max_imbalance
    # 计算最少交换次数：(imbalance + 1) // 2
    return (imbalance + 1) // 2

时间复杂度： O(n)，只需一次线性扫描。
空间复杂度： O(1)，只用了几个变量。

总结

这道题的精妙之处在于：

1. 转化问题：将“最少交换次数”转化为寻找遍历过程中 balance 的历史最小值。
2. 贪心结合DP：我们用一个状态变量 balance 线性地累积信息，这本质上是动态规划中“状态定义与转移”的思想。而“用后面的 '[' 交换前面的 ']'”是最优的贪心策略。
3. 公式推导：最终答案 (历史最小balance的绝对值 + 1) // 2 是一个非常简洁的结论，它来自于对一次交换能纠正两个单位不平衡度的观察。

它虽然代码简短，但完美地体现了线性动态规划中“用一维状态递推”和“从状态中提取最优解”的核心模式。