LeetCode-456 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.

Constraints

• \(1 \le n \le 2 \times 10^5\)
• \(-10^9 \le nums_i \le 10^9\)

Solution

枚举\(j\)，然后往2个容器（一个\(pre\)，一个\(suf\)）查询一下\(i\)和\(k\)就好了，\(O(nlogn)\)

Code

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size() < 3) return false;
        multiset<int> pre, suf;
        for(auto v : nums) suf.emplace(v);
        pre.emplace(nums[0]);
        suf.erase(suf.find(nums[0]));
        for(size_t i = 1; i < nums.size(); ++i) {
            suf.erase(suf.find(nums[i]));
            auto defer_op = [&](auto) {pre.emplace(nums[i]);};
            shared_ptr<void> _ {nullptr, defer_op};
            // 这是题面的j
            auto v = nums[i];
            // 从suf找出大于nums[i]小于nums[j]的k
            // 但这个时候其实没定好i
            // 从贪心的角度来看，找一个尽可能贴近j的k
            if(suf.empty()) continue;
            auto suf_iter = suf.lower_bound(v);
            // NOTE
            if(suf_iter == suf.begin()) continue;
            if(*--suf_iter >= v) continue;
            int vk = *suf_iter;

            // 随便找一个比nums[k]小的数
            if(*pre.begin() < vk) {
                return true;
            }
        }
        return false;
    }
};

Link

LeetCode-456 132 Pattern