題目描述:
給定一個由 '[' 和 ']' 組成的字串 s,其中左右括號數量相等。每次操作可以交換任意兩個位置的字元。求使字串成為平衡括號字串的最少交換次數。
解題思路:
unmatched 記錄未匹配的 '[' 數量。'[' 時 unmatched++;遇到 ']' 時,若 unmatched > 0 則匹配一對(unmatched--),否則這是一個多餘的 ']'。']]]...[[[' 的形式(先若干未匹配的 ']',再若干未匹配的 '[')。']' 數量為 unmatchedClose。每次交換可以修復 2 個未匹配的括號(一個 ']' 和一個 '[')。ceil(unmatchedClose / 2) = (unmatchedClose + 1) / 2。時間複雜度: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) / 2Stack 模擬法 O(n):用堆疊模擬匹配過程,遇到 ']' 且堆疊頂為 '[' 時彈出配對,最後堆疊中剩餘元素數 / 2 即為未匹配對數,答案同樣取上整除以 2。空間複雜度 O(n)。
雙指標法 O(n):左右指標分別找到最左的多餘 ']' 和最右的多餘 '[',直接交換。每次交換後兩指標向內移動。實際交換次數即為答案。
'(' 和 ')' 兩種括號,最少交換次數如何計算?