โปรแกรมหา Triplet nums[i] < nums[k] < nums[j] จากลิสต์ nums ใน C++

กำหนดให้มีลิสต์ตัวเลขชื่อ nums ต้องตรวจสอบว่ามี triplet (i, j, k) ที่ทำให้ i < j < k และ nums[i] < nums[k] < nums[j] หรือไม่

ตัวอย่าง

Input: nums = [2, 12, 1, 4, 4]
Output: True เพราะ [2, 12, 4] ตรงเงื่อนไข 2 < 4 < 12

อัลกอริทึม

1. สร้างอาร์เรย์ left ขนาด n โดย left[i] = ค่าต่ำสุดตั้งแต่ต้นถึง i
2. ใช้ Stack เก็บค่าจากขวาไปซ้าย
3. วนจากขวาไปซ้าย ตรวจสอบเงื่อนไข left[i-1] < nums[i] และ nums[i] > stack.top()
4. ถ้าเจอ ให้คืนค่า true

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

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

class Solution {
public:
    bool solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n);
        left[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            left[i] = min(nums[i], left[i - 1]);
        }
        
        stack<int> st;
        
        for (int i = n - 1; i >= 1; i--) {
            int x = left[i - 1];
            
            while (!st.empty() && st.top() <= x)
                st.pop();
            
            if (!st.empty() && x < nums[i] && nums[i] > st.top())
                return true;
            
            st.push(nums[i]);
        }
        
        return false;
    }
};

bool solve(vector<int>& nums) {
    return (new Solution())->solve(nums);
}

int main() {
    vector<int> v = {2, 12, 1, 4, 4};
    cout << solve(v);
}

ผลลัพธ์

1

คำอธิบาย: โค้ดคืนค่า 1 (true) เพราะพบ triplet (0, 1, 3) → nums[0]=2, nums[1]=12, nums[3]=4 ทำให้ 2 < 4 < 12 ตรงเงื่อนไข