解題說明
132 Pattern
題目描述:給定整數陣列 nums,判斷是否存在三個索引 i < j < k,使得 nums[i] < nums[k] < nums[j](即 132 模式:最小在最左,最大在中間,中間值在最右)。若存在回傳 true,否則回傳 false。
解題思路:從右向左掃描,利用單調棧維護「132 模式中的 nums[k](第三個值,即中間大小)」。
維護一個單調遞減棧和一個變數 third(代表目前見過的最大可能 nums[k],初始為 INT_MIN)。從右向左掃描每個元素 cur:
- 若
cur < third,代表找到了比third更小的值作為nums[i],且third已是一個合法的中間值,132 模式成立,回傳true。 - 否則,將棧中所有小於
cur的元素彈出並更新third(這些被彈出的元素是候選的nums[k],cur是對應的nums[j])。 - 將
cur推入棧。
核心觀察:棧維護從右往左的單調遞減序列,代表潛在的 nums[j] 候選;被彈出的元素成為 third(nums[k]),未來若遇到更小的 cur 即為 nums[i]。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個元素最多入棧一次、出棧一次,從右向左一次線性掃描完成。
空間複雜度:O(n) — 單調棧最多儲存 n 個元素(當陣列嚴格遞減時,所有元素都會在棧中)。
虛擬碼
1. Initialize stack stk (empty), third = INT_MIN.
2. For i from n-1 down to 0:
a. If nums[i] < third: return true.
b. While stk not empty and stk.top() < nums[i]:
- third = stk.top(); pop stk.
c. Push nums[i] onto stk.
3. Return false.其他解法
方法一:二分搜尋 + 有序集合
從右向左掃描,用 std::multiset 維護右側的有序元素集合。對每個 nums[j](固定中間最大值):在集合中二分搜尋大於 min_left[j](前綴最小值)且小於 nums[j] 的元素。時間 O(n log n),空間 O(n),比單調棧慢。
方法二:暴力三重迴圈
枚舉所有三元組 (i, j, k) 檢查是否滿足條件。時間 O(n^3),空間 O(1)。只適合 n ≤ 100 的情況。
方法三:前綴最小 + 二分搜尋
預計算 minLeft[i](nums[0..i] 的最小值),從左到右固定 j,在 nums[j+1..n-1] 中用二分搜尋找到介於 minLeft[j] 和 nums[j] 之間的值。時間 O(n log n),需預先建立有序結構,不如單調棧簡潔。
延伸思考
- 若改為找 123 模式(嚴格遞增三元組),問題等價於最長遞增子序列(LIS)的長度是否 ≥ 3,有何更快的解法?
- 若要求找出所有滿足 132 模式的三元組,而非只判斷是否存在,時間複雜度的下界是多少?
- 本題的「從右向左掃描 + 單調棧追蹤最優候選」技巧,在股票問題(如 LeetCode 84 柱狀圖最大矩形)中也有體現,兩者的核心思路有何共通之處?