456. 132模式
2021年3月24日
1e4的数据，我\(O(n^2)\)都能给你过了，就不能1e5的数据吗
单调栈经典例题(๑•̀ㅂ•́)و√
倒着遍历，维护一个递减的单调栈。
两个方法：
第一个方法
- 记录所有从栈里弹出的所有数的最大值\(maxx\)，这个是2
- 栈顶就是3
- 将要进的值\(nums[i]\)，如果\(<maxx\)，那么这个值就是1
- 否则就进栈。
- 这样子可以一直保证，\(maxx\)是2，栈顶是3
class Solution {
private:
stack<int>q;
public:
bool find132pattern(vector<int>& nums) {
int maxx=INT_MIN;
int n=nums.size();
for(int i=n-1;i>=0;i--){
if(maxx>nums[i])
return true;
while(!q.empty()&&q.top()<nums[i])
maxx=max(maxx,q.top()),q.pop();
q.push(nums[i]);
}
return false;
}
};
第二个写法
- 首先先正着遍历，记录\(nums[i]\)前的最小值，记录到\(v[i]\)里。
- 依然是维护一个递减的单调栈
- 倒着遍历，这里注意的是，我们比较的是栈顶和\(v[i]\)的大小
- 如果栈顶小于等于\(v[i]\)，显然栈顶不符合2的条件，故将其弹出
- 当栈顶大于\(v[i]\)时，栈顶符合2的条件
- 再比较即将进入的\(nums[i]\)和栈顶的大小，如果栈顶小，我们就找到了答案
class Solution {
private:
stack<int>q;
public:
bool find132pattern(vector<int>& nums) {
int maxx=INT_MIN;
int n=nums.size();
vector<int>v(n);
v[0]=nums[0];
for(int i=1;i<n;i++)
v[i]=min(v[i-1],nums[i-1]);
for(int i=n-1;i>=0;i--){
while(!q.empty()&&q.top()<=v[i])
q.pop();
if(!q.empty()&&q.top()<nums[i])
return true;
q.push(nums[i]);
}
return false;
}
};