MediumRating 1689
1963. Minimum Number of Swaps to Make the String Balanced
two-pointersstringstackgreedy
解題說明
Minimum Number of Swaps to Make the String Balanced
題目描述：
給定一個由 '[' 和 ']' 組成的字串 s，其中左右括號數量相等。每次操作可以交換任意兩個位置的字元。求使字串成為平衡括號字串的最少交換次數。
解題思路：
- 先用貪心消除所有已經匹配的括號對：遍歷字串，維護一個計數器
unmatched記錄未匹配的'['數量。 - 遇到
'['時unmatched++；遇到']'時，若unmatched > 0則匹配一對（unmatched--），否則這是一個多餘的']'。 - 消除後，剩下的必定是
']]]...[[['的形式（先若干未匹配的']'，再若干未匹配的'['）。 - 設未匹配的
']'數量為unmatchedClose。每次交換可以修復 2 個未匹配的括號（一個']'和一個'['）。 - 因此答案為
ceil(unmatchedClose / 2)=(unmatchedClose + 1) / 2。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單次遍歷字串。
空間複雜度：O(1) — 只使用兩個計數器。
虛擬碼
1. Initialize unmatchedOpen = 0, unmatchedClose = 0
2. For each character c in s:
a. If c == '[': increment unmatchedOpen
b. If c == ']':
- If unmatchedOpen > 0: decrement unmatchedOpen (matched pair)
- Else: increment unmatchedClose (extra ']')
3. Return ceil(unmatchedClose / 2) = (unmatchedClose + 1) / 2其他解法
Stack 模擬法 O(n)：用堆疊模擬匹配過程，遇到 ']' 且堆疊頂為 '[' 時彈出配對，最後堆疊中剩餘元素數 / 2 即為未匹配對數，答案同樣取上整除以 2。空間複雜度 O(n)。
雙指標法 O(n)：左右指標分別找到最左的多餘 ']' 和最右的多餘 '['，直接交換。每次交換後兩指標向內移動。實際交換次數即為答案。
延伸思考
- 如果字串中還包含
'('和')'兩種括號，最少交換次數如何計算？ - 如果限制只能交換相鄰字元，最少交換次數是多少？
- 如何實際輸出每次交換的位置對？