132 patten

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

• stack只需要放一个数字(看discuss看来的- -）

  class Solution {
  public:
    bool find132pattern(vector<int>& nums) {
        stack<int> sta;
        int right_min = INT_MIN;
        for(int i = nums.size() -1; i >=0; --i) {
            if (nums[i]<right_min) return true;
            else {
                while(!sta.empty() && sta.top() < nums[i]) {
                    right_min = max(right_min, sta.top());
                    sta.pop();
                }
                sta.push(nums[i]);
            }
        }
        return false;
    }
  };
  

• stack还是要放一个pair，看discuss看到需要用stack，然后自己想到的- -

  class Solution {
  public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size() <=2)return false;
        stack<pair<int,int>> sta;
        int i = 1;
        int prev_min = nums[0];
        while(i< nums.size()) {
            while(!sta.empty() && sta.top().first <= nums[i]) {
                sta.pop();
            }
            if(!sta.empty() && sta.top().first > nums[i] && sta.top().second < nums[i]) return true;
            sta.push(make_pair(nums[i],prev_min));
            prev_min=min(prev_min,nums[i++]);
        }
        return false;
    }
  };