leetcode 456. 132 Pattern 132模式元素寻找 + 一个很棒的利用stack的做法

分手后的思念是犯贱 2022-06-04 09:08 146阅读 0赞

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\].

思路是我们维护一个栈和一个变量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值小这个条件，

参考链接：[leetcode 456][]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool find132pattern(vector<int>& nums) 
        {
            int third = numeric_limits<int>::min();
            stack<int> sk;
            for (int i = nums.size() - 1; i >= 0; i--)
            {
                if (nums[i] < third)
                    return true;
                else
                {
                    while (sk.empty() == false && nums[i] > sk.top())
                    {
                        third = sk.top();
                        sk.pop();
                    }
                    sk.push(nums[i]);
                }
            }
            return false;
        }
    };

[leetcode 456]: https://www.cnblogs.com/grandyang/p/6081984.html