题目描述

blablabla

样例

blablabla

第一次在acwing写题解,若有错误,欢迎指正.

这个题有两种解法(如果不算暴力的话…) 蒟蒻的我都是看题解才能理解的QAQ,树状数组的那种解法是很好理解的,所以
不在过多赘述了
1. 思路1:树状数组O(nlogn)
转自
2. 思路2:单调栈O(n)
关于单调栈的做法,思路还是很好理解的,但是在利用单调栈做题的时候,发现这个题利用单调栈枚举时不太好确定
在维护弹出栈的时候是否这些出栈元素会对后面的判断产生影响,所以这里主要是给出一个我自己想的证明,可能不太严谨,
会有漏洞,欢迎dalao们可以提出错误,当然,如果可以帮忙对证明进行修正补充的话更是极好的,不多说废话了,下文进行证明

假设在 j 之前入栈的元素所弹出的元素可以与 j 和 min[j] 组成 132 模式, 那么一定满足 该元素 > min[j] 且 num[j] > 该元素, 而min[k] <= min[j] 并且可以发现由于该元素是由k位置的数入栈时弹出的, 必然满足num[k] > 该元素 而由 min[k] <= min[j] 又可以得出, 该元素一定 > min[k] 也就是说, 若当前元素可以与 j 和 min[j] 组成 132 模式的话, 之前一定存在一个 k 已经可以构成 132 模式, 必然不会枚举到 j 这个位置, 故可以得出结论: 对于 j 之前所有元素入栈时所弹出的元素一定对于判断当前是否存在解是无效的

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int>sta;
        if (nums.size() < 3) return false;
        int *Min = new int[nums.size()];
        Min[0] = nums[0];
        int right = INT_MIN;
        for (int i = 1; i < nums.size(); i++) Min[i] = min(Min[i - 1], nums[i - 1]);
        for (int i = nums.size() - 1; i; i--) {
            if (!sta.size() || sta.top() >= nums[i]) sta.push(nums[i]);
           else {
                while (sta.size() && sta.top() < nums[i]) right = sta.top(), sta.pop();
                if (Min[i] < right) return true;
                sta.push(nums[i]);
           }
        }
        return false;
    }
};