Mẫu 132 Trong C++

Giả sử chúng ta có dãy n số nguyên a1, a2, ..., an. Một mẫu 132 là dãy con ai, aj, ak sao cho i < j < k và ai < ak < aj. Thiết kế thuật toán kiểm tra xem danh sách n số có chứa mẫu 132 hay không. Ví dụ, [-1, 3, 2, 0] trả về true vì có các mẫu [-1,3,2], [-1,3,0], [-1,2,0].

Để giải quyết, chúng ta làm theo các bước:

n := kích thước nums, nếu n == 0 trả về false.
Tạo mảng minVals kích thước n, minVals[0] = nums[0].
Với i từ 1 đến n-1: minVals[i] = min(minVals[i-1], nums[i]).
Tạo stack s.
Với i từ n-1 xuống 1: minVal = minVals[i-1], curr = nums[i].
Khi s không rỗng và s.top() <= minVal: s.pop().
Nếu s không rỗng và s.top() < curr, trả về true.
Đẩy nums[i] vào s.
Trả về false.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

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

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

int main(){
    vector<int> v = {-1,3,2,0};
    Solution ob;
    cout << (ob.find132pattern(v));
}

Đầu vào

[-1,3,2,0]

Mẫu 132 Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra