原题传送门:->132 Pattern

Description：

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

函数模板:

class Solution {
public:
    bool find132pattern(vector<int>& nums) {

    }
};

思路：
1、对于nums[j]，如何判断存在nums[i]、numsk，满足题意呢？
只需要:

  • ①找到j左侧的最小值nums[i]
  • ②找到j右侧的、大于nums[i]的最小值nums[k]
  • ③满足nums[j]>nums[k]

①遍历一次就可以在O(1)内完成。

    vector<int>pre_min;
    int creatPreMin(vector<int>& nums){
        pre_min.resize(nums.size());
        pre_min[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i){
            pre_min[i] = (pre_min[i-1] > nums[i])? nums[i]: pre_min[i-1];
        }
        return 0;
    }
//pre_min[i]记录了nums[i]左侧的最小值

③仅需一步比较。

难点在于②，因为nums[i]是一直变化的，假如nums[i]每次变化后都通过遍历寻找最小值，复杂度就变成O(N^2)了，会超时。

那么——如何在O(N)内完成操作②呢？这里引入单调栈。

该题的递减栈有以下特点:
1、入栈为递减(出栈为递增)
2、栈顶元素即为需要找的“nums[k]”(j右侧的、大于nums[i]的最小值)

更新递减(非递增)栈的策略:

  • 1)从右往左遍历，下标为i
  • 2)当nums[i] <= pre_min[i]，直接遍历下一个。
  • 3)若栈顶元素小于等于pre_min[i], 不断弹栈(栈顶元素不断增大)直到栈顶元素大于pre_min[i]为止

解释一下2)3)：pre_min[i]是非递增序列，倒叙遍历时是非递减的，所以小于等于pre_min[i]的值在之后的遍历中也一定小于等于pre_min[i]，一定不满足题意。

  • 4)若nums[i]大于栈顶元素，则答案为True，直接return
  • 5)其他情况则入栈。（由于4)的处理，nums[i]一定小于等于栈顶元素，所以栈仍为递减(非递增)）
class Solution {
public:
    vector<int>pre_min;
    bool find132pattern(vector<int>& nums) {
        creatPreMin(nums);
        stack<int>S;
        for(int i = nums.size()-1; i > 0; --i){
            if(nums[i] > pre_min[i]){
                while(!S.empty() && S.top() <= pre_min[i]) S.pop();
                if(!S.empty()&&(nums[i] > S.top())) return true;
                S.push(nums[i]);
            }
        }
        return false;
    }
    int creatPreMin(vector<int>& nums){
        pre_min.resize(nums.size());
        pre_min[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i){
            pre_min[i] = (pre_min[i-1] > nums[i])? nums[i]: pre_min[i-1];
        }
        return 0;
    }
};