LeetCode 456 Pattern

Posted on | In | 阅读

单调栈，找到132这种大小关系的子序列

暴力的方法需要O(N^3)的复杂度，但是利用单调栈就可以达到O(N)

从右向左扫描整个数组，其实我们只需要把当前扫描到的数当作(1)，维护当前最大的(2)即可，只要(1) < (2)就是找到。

维护一个单调队列，栈顶小栈底大，每次pop时都相当于找到了一个(2)(3)pair，维护pop的值的最大值就是我们要的(3)

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int sz = nums.size();
        if(sz < 3) {
            return false;
        }
        stack<int> st;
        int ak = INT_MIN;
        st.push(nums[sz-1]);
        for(int i = sz-1; i >= 0; --i) {
            if(nums[i] < ak) {
                return true;
            }
            while(!st.empty() && nums[i] > st.top()) {
                ak = max(ak, st.top());
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};