本文主要是介绍132 模式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
456. 132 模式
给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。
如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,4]
输出:false
解释:序列中不存在 132 模式的子序列。
来源:力扣(LeetCode)
看见这题的时候我就猜到应该能用单调栈,但就是写不出来,难受,过了半个月,回头来写还是写不出,无奈之中只能看题解了,再大佬题解的帮助下,总算是搞懂了
思路:不找132,而是反向遍历找231
要找132的话,找的是2,因此既要满足>1,又要满足<3
而找231的话,找的是1,因此只要小于2即可
那么怎么利用单调栈找到23呢?很明显23递增,那么我们维护一个递减栈(从顶到底递减),当栈里一直是递减的时候,就不可能会出现23,因为23是递增,但是一旦有一个数破坏了栈的单调性,那么就该干活了,因为此时已经有了若干对23了,3是破坏单调的(即当前遍历到)的元素,而此时栈内的所有小于3的元素都能当作2,我们要找的是小于2的数,那么再若干个2里,我们必须取最大的一个,这样才能保证覆盖所有情况
然后为了不影响站的单调性,我们一边弹出栈顶一边取最大的2值
这里注意一下,因为我们这种找2的方法,所以每一个2都一定是有效的,因为前面一定有比它还大的3存在
然后就差一步判断当前元素是否小于最大的2了,这一步必须放在最开始,不然的话,最大2可能因为当前元素更新,这时再判断,就晚了
class Solution {
public:bool find132pattern(vector<int>& nums) {stack<int>st;int val = INT_MIN;//储存最大2for(int i = nums.size()-1;i>=0;--i){//反向遍历找231if(nums[i]<val)return true;//因为初始化为INT_MIN,所以不会有问题while(!st.empty() && nums[i]>st.top()){//维护单调性val = max(val,st.top());st.pop();//取最大2}st.push(nums[i]);//将当前数字存入栈}return false;}
};
这篇关于132 模式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!