Chương trình tìm bộ ba nums[i] < nums[k] < nums[j] trong C++

Mô tả bài toán

Cho danh sách số nums, kiểm tra xem có tồn tại bộ ba chỉ số (i, j, k) với i < j < k và nums[i] < nums[k] < nums[j] hay không.

Ví dụ: nums = [2, 12, 1, 4, 4] → True vì bộ ba [2, 12, 4] thỏa 2 < 4 < 12.

Giải thuật

1. Tính mảng left[i] = min(nums[0..i]).
2. Duyệt từ phải sang trái (i từ n-1 xuống 1), dùng stack để lưu các giá trị nums[i] ứng viên cho nums[j].
   • x = left[i-1].
   • Pop khỏi stack các phần tử ≤ x.
   • Nếu stack không rỗng và x < nums[i] và nums[i] > stack.top() → trả về true.
   • Push nums[i] vào stack.
3. Trả về false nếu không tìm thấy.

Ví dụ minh họa (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);
    return 0;
}

Đầu vào

{2, 12, 1, 4, 4}

Đầu ra

1