給定整數陣列
nums，判斷是否存在三個索引i < j < k使得nums[i] < nums[k] < nums[j]（即 132 模式）。
Example:
Input: nums = [3,1,4,2] Output: true
Intuition
TIP
核心思路：從右往左掃描，用遞減單調堆疊維護候選的 nums[j]，被彈出的最大值作為 nums[k]，遇到比 nums[k] 小的就找到 132 模式。
- 132 模式需要
nums[i] < nums[k] < nums[j]，其中 i < j < k - 從右往左掃描，堆疊維護「遞減序列」代表可能的
nums[j] - 被彈出的元素中最大的就是最佳的
nums[k]（第二大的候選值） - 當前元素若小於
nums[k]，就構成了nums[i]
Approaches
1. Brute Force — O(n^3) / O(1)
- Idea: 枚舉所有 (i, j, k) 三元組，檢查是否滿足 132 模式
- Time:
O(n^3) - Space:
O(1)
class Solution {
fun find132pattern(nums: IntArray): Boolean {
val n = nums.size
for (i in 0 until n - 2) {
for (j in i + 1 until n - 1) {
for (k in j + 1 until n) {
if (nums[i] < nums[k] && nums[k] < nums[j]) {
return true
}
}
}
}
return false
}
}⭐ 2. Monotonic Stack Right-to-Left — O(n) / O(n)
- Idea: 從右往左遍歷，維護遞減堆疊。新元素大於棧頂時，持續 pop 並更新
third（132 中的 2）。若當前元素 <third，則找到答案 - Time:
O(n)- 每個元素最多入棧出棧各一次 - Space:
O(n)
class Solution {
fun find132pattern(nums: IntArray): Boolean {
val n = nums.size
val stack = ArrayDeque<Int>()
var third = Int.MIN_VALUE // 132 中的 "2"（nums[k]）
for (i in n - 1 downTo 0) {
// 當前元素是候選的 "1"（nums[i]）
if (nums[i] < third) return true
// 當前元素是候選的 "3"（nums[j]），比棧頂大就彈出
while (stack.isNotEmpty() && nums[i] > stack.last()) {
third = stack.removeLast()
}
stack.addLast(nums[i])
}
return false
}
}WARNING
third 變數的初始值必須是 Int.MIN_VALUE，代表還沒有找到有效的 “2”。third 是單調非遞減的（只會變更大），因為堆疊是遞減的，後彈出的一定比先彈出的大。
🔑 Takeaways
- Pattern: 尋找特定大小順序的子序列，反向遍歷搭配單調堆疊可以高效解決
- Key trick: 從右往左掃描，堆疊中是「3」的候選，被彈出的最大值是「2」的最佳選擇，當前元素是「1」的候選。
third只增不減保證了正確性