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

Solution

Brute Force
Time complexity : O(n^3)
Space complexity : O(1)

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        for (int i=0; i<n-2; ++i) {
            for (int k=i+1; k<n-1; ++k) {
                for (int j=k+1; j<n; ++j) {
                    if (nums[i] < nums[j] && nums[j] < nums[k])
                        return true;
                }
            }
        }
        return false;
    }
};

很直覺，暴力把所有情況都跑一遍。

Better than brute force
Time complexity : O(n^2)
Space complexity : O(1)

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        int min_i = INT_MAX;
        
        for (int k=0; k<n-1; ++k) {
            min_i = min(min_i, nums[k]);
            for (int j=k+1; j<n; ++j) {
                if (min_i < nums[j] && nums[j] < nums[k])
                    return true;
            }
        }
        
        return false;
    }
};

比brute force好一點點，從左往右掃，多了記錄到目前為止的最小值。

Searching Intervals
Time complexity : O(n^2)
Space complexity : O(n)

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> intervals;
        
        int i = 0;
        for (int j=1; j<n; ++j) {
            if (nums[j-1] > nums[j]) {
                if (i < j-1)
                    intervals.push_back({nums[i], nums[j-1]});
                i = j;
            }
            for (const pair<int, int> min_max: intervals) {
                if (min_max.first < nums[j] && nums[j] < min_max.second)
                    return true;
            }
        }
        
        return false;
    }
};

考量的掃描點是j，第二大的。
想法是只要遇到數值下坡(前一個比現在的大)，且i點在前2個以前，就將目前的i和最大值(前一個)塞入存放可能是答案的容器中。

再利用目前的j點，與所有可能是答案的i、k點去比對，看是否有答案出現。

Stack
Time complexity : O(n)
Space complexity : O(n)

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        vector<int> min_val;
        stack<int> stk;
        
        for (int idx=0; idx<n; ++idx) {
            if (0==idx) min_val.push_back(nums[idx]);
            else {
                min_val.push_back(min(nums[idx], min_val.back()));
            }
        }
        
        for (int k=n-1; 0<=k; --k) {
            if (min_val[k] < nums[k]) {
                while (!stk.empty() && min_val[k] >= stk.top()) stk.pop();
                if (!stk.empty() && stk.top() < nums[k]) return true;
                stk.push(nums[k]);
            }
        }
        
        return false;
    }
};

此處用的stack，定義只能往疊放越來越小的值(j)。
事先從頭往後記錄當前為止最小的值(i)。

接下來從尾往前，一個一個試k，
此處min_val[k]可視為i值，
首先調整stack到合適的狀態，即i值 < j值，將有i值 >= j值pop掉。
判斷目前的k值是否為答案，不是的話將其塞入stack中。