解題說明
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 柱狀圖最大矩形）中也有體現，兩者的核心思路有何共通之處？