Solution: 132 Pattern

   132 Pattern

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

 

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

 

Constraints:

• n == nums.length
• 1 <= n <= 104
• -109 <= nums[i] <= 109

..

Tìm bộ số thỏa mãn 2 điều kiện là: i<j<k và a[i]<a[k]<a[j]

Gọi mảng minArr với minArr[i] là giá trị min trong đoạn (0,i-1), tạo một stack lưu giá trị lớn hơn giá trị minArr hiện thời, bất cứ khi nào stack.top()<=minArr[i] thì đẩy hết stack ra, như thế, ta luôn có: 

minArr(i) < stk.top() và vì minArr[i] lưu giá trị min trong đoạn (0,i-1) vậy minArr(i) ở đây chính là a[i], stk.top() là a[k], còn a[j] thì thế nào ?

Vì ta duyệt từ cuối mảng, nên stk.top() luôn nào cũng nằm trước phần tử arr[i], vậy chỉ khi nào stk.top()<arr[i] thì ta sẽ tìm được 1 cặp như vậy.

Chỉ cẩn nhớ: minArr[i] < stk.top() < arr[i].

Sourcecode:

class Solution {

public:

    bool find132pattern(vector<int>& nums) {

        if (nums.size()<3){

            return false;

        }

        

        vector<int> minArr(nums.size(),INT_MAX);

        stack<int> stk;

        

        for (int i=1; i<nums.size(); i++){

            minArr[i] = min(minArr[i-1],nums[i-1]);

        }

        

        for (auto i:minArr){

            cout << i << " ";

        }

        

        cout << endl;

        

        for (int i=nums.size()-1; i>=0; i--){

            while (!stk.empty() && stk.top()<=minArr[i]){

                stk.pop();

            }    

            

            if (!stk.empty() && stk.top()<nums[i]){

                cout << stk.top() << " " << nums[i] << " " << i;

                return true;

            }

            

            stk.push(nums[i]);

        }

        

        return false;      

    }

};