題目來源
給一個數(shù)組痢虹，判斷數(shù)組中是否存在132模式的三個元素被去。
我一開始想著n方的方法奖唯，就是遍歷一遍惨缆，然后每次從左找比當(dāng)前元素小的丰捷，從右開始找比當(dāng)前元素大的。代碼如下：
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
for (int i=2; i<n; i++) {
int l = 0, r = i - 1;
while (l < r) {
if (nums[l] < nums[i] && nums[r] > nums[i]) {
return true;
}
if (nums[l] >= nums[i])
l++;
if (nums[r] <= nums[i])
r--;
}
}
return false;
}
};
然后就超時(shí)了==病往，然后看了下tags，里面寫著棧停巷！
然后還是沒想出來怎么做耍攘，看了下討論區(qū)畔勤，
實(shí)際上就是從后往前遍歷，存儲著一個棧庆揪，棧中元素都比當(dāng)前值大式曲，假如比當(dāng)前元素小的話嚷硫，那么就退棧，然后當(dāng)前元素進(jìn)棧仔掸。
然后s3是最后一個退棧的元素脆贵。
遍歷的時(shí)候比較當(dāng)前元素和s3的大小起暮。
維持棧頂元素大于s3，并且序列棧頂元素小于s3负懦。
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int s3 = INT_MIN;
int n = nums.size();
stack<int> s;
for (int i=n-1; i>=0; i--) {
if (nums[i] < s3)
return true;
else {
while (!s.empty() && nums[i] > s.top()) {
s3 = s.top();
s.pop();
}
s.push(nums[i]);
}
}
return false;
}
};
