456. 132 Pattern

 

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.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

 

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

 

Example 3:

Input: [-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].

 

这道题给了一个数组,让我们找到 132 的模式,就是第一个数小于第二第三个数,且第三个数小于第二个数。当然最直接最暴力的方法,就是遍历所有的三个数字的组合,然后验证是否满足这个规律。得莫,OJ 说打妹。那么就只能想办法去优化了,由于暴力搜索的时间复杂度是三次方,在之前的 3Sum 那道题中,也有把立方的复杂度减少到平方的复杂度,相当于降了一维(降维打击么?),其实就是先固定一个数字,然后去遍历另外两个数字。先确定哪个数字呢,当然是最小的那个啦,这里维护一个变量 mn,初始化为整型最大值,然后在遍历数字的时候,每次用当前数字来更新 mn,然后判断,若 mn 为当前数字就跳过,因为需要找到数字j的位置,数字j是大于数字i的,mn 表示的就是数字i。这样数字i和数字j都确定了之后,就要来遍历数字k了,范围是从数组的最后一个位置到数字j之间,只要中间的任何一个数字满足题目要求的关系,就直接返回 true 即可,参见代码如下:

 

解法一:

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

 

那么就按顺序来找这三个数,首先来找第一个数,这个数需要最小,如果发现当前数字大于等于后面一个数字,就往下继续遍历,直到当前数字小于下一个数字停止。然后找第二个数字,这个数字需要最大,如果发现当前数字小于等于下一个数字就继续遍历,直到当前数字大于下一个数字停止。最后就找第三个数字,验证这个数字是否在之前两个数字的中间,如果没有找到,就从第二个数字的后面一个位置继续开始重新找这三个数字,参见代码如下:

 

解法二:

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

 

下面这种方法利用单调栈来做,既简洁又高效,关于单调栈可以参见博主之前的一篇文章 LeetCode Monotonous Stack Summary 单调栈小结。思路是维护一个栈和一个变量 third,其中 third 就是第三个数字,也是 pattern 132 中的2,初始化为整型最小值,栈里面按顺序放所有大于 third 的数字,也是 pattern 132 中的3,那么在遍历的时候,如果当前数字小于 third,即 pattern 132 中的1找到了,直接返回 true 即可,因为已经找到了,注意应该从后往前遍历数组。如果当前数字大于栈顶元素,那么将栈顶数字取出,赋值给 third,然后将该数字压入栈,这样保证了栈里的元素仍然都是大于 third 的,想要的顺序依旧存在,进一步来说,栈里存放的都是可以维持坐标 second > third 的 second 值,其中的任何一个值都是大于当前的 third 值,如果有更大的值进来,那就等于形成了一个更优的 second > third 的这样一个组合,并且这时弹出的 third 值比以前的 third 值更大,为什么要保证 third 值更大,因为这样才可以更容易的满足当前的值 first 比 third 值小这个条件,举个例子来说吧,比如 [2, 4, 2, 3, 5],由于是从后往前遍历,所以后三个数都不会进入 while 循环,那么栈中的数字为 5, 3, 2(其中2为栈顶元素),此时 third 还是整型最小,那么当遍历到4的时候,终于4大于栈顶元素2了,那么 third 赋值为2,且2出栈。此时继续 while 循环,因为4还是大于新栈顶元素3,此时 third 赋值为3,且3出栈。现在栈顶元素是5,那么 while 循环结束,将4压入栈。下一个数字2,小于 third,则找到符合要求的序列 [2, 4, 3],参见代码如下:

 

解法三:

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

 

讨论:这道题的一个很好的 Follow up 就是求出所有 132 模式的数组,想来想去也没啥特别好的方法,这里的三种解法都不适用,难道只能用暴力搜索了么。

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/456

 

参考资料:

https://leetcode.com/problems/132-pattern/

https://leetcode.com/problems/132-pattern/discuss/94135/c_ac

https://leetcode.com/problems/132-pattern/discuss/94133/Simple-java-accepted-well-explained-O(n2)-solution

https://leetcode.com/problems/132-pattern/discuss/94071/single-pass-c-on-space-and-time-solution-8-lines-with-detailed-explanation

https://leetcode.com/problems/132-pattern/discuss/94089/Java-solutions-from-O(n3)-to-O(n)-for-%22132%22-pattern-(updated-with-one-pass-slution)

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation