456find132pattern

555,BF失败！

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

一种好方法

运用上面的思路，可以对算法进行简化操作

我们先找到i和j，让nums[i]<nums[j]然后再在nums[j+1]到尾部找到夹在他们两之间的nums[k]

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size()<3) return false;
        int i=0;//1模式
        int j=0;//3模式
        int k=0;//2模式
        int n=nums.size();
        while(i<n)
        {
            //这一步是找到前i个中的最小值，作为1
            while(i<n-2 && nums[i]>=nums[i+1]) i++;
            j=i+1;
            //这一步是找到第i到j中最大的，这里已经比nums[i]大了
            while(j<n-1 && nums[j]<=nums[j+1]) j++;
            k=j+1;
            while(k<n)
            {
                if(nums[k]<nums[j] && nums[k]>nums[i])
                    return true;
                else k++;
            }
            //如果没找到的话，那就进行第二次遍历
            //i到j之间已经不存在情况了
//比如4，3，2，1，9，10，11，-1，100;  i是1，j是11既然1-11都没有
//那么1-9，1-10更加不会有，所以从i=j+1开始探索           
            i=j+1;
        }
        return false;
    }
};

用栈存放最大的元素，次大的元素用third存放，遍历方式从后往前。若找到比third小的元素则说明存在132模式。

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size()<3) return false;
        stack<int> max;
        int n=nums.size();
        int third=INT_MIN;
        //初始化不能为0，因为要进行比较，初始化为0会出错。
        for(int i=n-1;i>=0;i--)
        {
            if(nums[i]<third) return true;
            while(!max.empty() && nums[i]>max.top())
	//若找到比栈中还大的元素，则更新最大和次大，次大和最大靠地越近，那么就越有可能找到1
            {
                third=max.top();
                max.pop();
            }
            max.push(nums[i]);
        }
        return false;
    }
};