132 Pattern ใน C++ : หาลำดับย่อย ai < ak < aj

ให้ Array nums หาว่ามี **132 Pattern** หรือไม่ คือ มี Index i < j < k ทำให้ nums[i] < nums[k] < nums[j]

ตัวอย่าง

[-1, 3, 2, 0] -> true

Patterns: [-1, 3, 2], [-1, 3, 0], [-1, 2, 0]

แนวทาง: Monotonic Stack + Prefix Min (O(N))

1. Precompute minVals[i] = Min value จาก nums[0..i] (ค่า ai ที่เล็กที่สุดทางซ้าย)
2. Iterate จาก **ขวาไปซ้าย (j = n-1 downto 1)**:
   • minVal = minVals[j-1] (Best ai สำหรับ aj นี้)
   • curr = nums[j] (เป็น aj)
   • Maintain **Decreasing Stack** ของ Candidate ak (ค่าที่ > minVal และ < curr)
   • Pop Stack จน top > minVal
   • ถ้า Stack ไม่ว่าง และ top < curr -> เจอ 132 Pattern (minVal < top < curr) -> Return true
   • Push curr เข้า Stack (เป็น Candidate ak สำหรับ aj ทางซ้าย)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (!n) return false;

        // 1. Prefix Min
        vector<int> minVals(n);
        minVals[0] = nums[0];
        for (int i = 1; i < n; i++)
            minVals[i] = min(minVals[i-1], nums[i]);

        // 2. Scan from right with Decreasing Stack
        stack<int> st;
        for (int i = n - 1; i > 0; i--) {
            int minVal = minVals[i - 1]; // Best ai for this aj
            int curr = nums[i];          // Current aj

            // Pop values <= minVal (cannot be ak since ak > ai)
            while (!st.empty() && st.top() <= minVal)
                st.pop();

            // If stack has value < curr -> found 132: minVal < st.top() < curr
            if (!st.empty() && st.top() < curr)
                return true;

            st.push(curr); // curr becomes candidate ak for left elements
        }
        return false;
    }
};

Input / Output

Input:  [-1,3,2,0]
Output: 1 (true)

ความซับซ้อน (Complexity)

• Time: O(N) — แต่ละ Element Push/Pop Stack สูงสุด 1 ครั้ง
• Space: O(N) — MinVals Array + Stack

Intuition ของ Stack

Stack เก็บ **Candidate สำหรับ ak** (ค่าระหว่าง ai และ aj) โดยรักษา **Decreasing Order** เพราะเราต้องการ ak ให้ **ใหญ่ที่สุดเท่าที่จะเป็นได้ (แต่ยัง < aj)** เพื่อโอกาสเจอ Pattern สูงสุด การ Pop ค่าที่ ≤ minVal ทำให้ Stack มีเฉพาะค่าที่ > ai (minVal) เท่านั้นครับ