456. 132 Pattern

Medium

Description

給定整數陣列 nums，判斷是否存在三個索引 i < j < k 使得 nums[i] < nums[k] < nums[j]（即 132 模式）。

Example:

Input: nums = [3,1,4,2] Output: true

Intuition#

核心思路：從右往左掃描，用遞減單調堆疊維護候選的 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#

概念: 枚舉所有 (i, j, k) 三元組，檢查是否滿足 132 模式
時間複雜度: O(n^3)
空間複雜度: 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: 從右往左單調堆疊#

概念: 從右往左遍歷，維護遞減堆疊。新元素大於棧頂時，持續 pop 並更新 third（132 中的 2）。若當前元素 < third，則找到答案
時間複雜度: O(n) - 每個元素最多入棧出棧各一次
空間複雜度: 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
    }
}

🔑 Takeaways#

Pattern: 尋找特定大小順序的子序列，反向遍歷搭配單調堆疊可以高效解決
關鍵技巧: 從右往左掃描，堆疊中是「3」的候選，被彈出的最大值是「2」的最佳選擇，當前元素是「1」的候選。third 只增不減保證了正確性