C++ 中的 132 模式
c++server side programmingprogramming
假设我们有一个由 n 个整数组成的序列 a1、a2、...、an，132 模式是子序列 ai、aj、ak，其中 i < j < k 且 ai < ak < aj。因此，我们必须设计一个算法，以 n 个数字的列表作为输入，并检查列表中是否存在 132 模式。因此，例如，如果输入为 [-1, 3, 2, 0]，则输出将为 true，因为有三种模式 [-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0]。
为了解决这个问题，我们将遵循以下步骤 −
n := nums 的大小，如果 n 为 0，则返回 false
定义一个名为 minVals 的大小为 n 的数组，设置 minVals[0] := nums[0]
对于 I 在 1 到 n 的范围内 – 1
minVals[i] := minVals[i - 1] 和 nums[i] 中的最小值
创建堆栈 st
for I in range n – 1 down to 1
minVal := minVals[i – 1]
curr := nums[j]
当 st 不为空且堆栈顶部 <= minVal
从堆栈 st 中删除
如果 st 不为空且堆栈顶部 < curr，则返回 true
将 nums[i] 插入到 s 中
return false
Example (C++)
让我们看下面的实现，以便更好地理解 −
-->
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(!n) return false;
vector <int> minVals(n);
minVals[0] = nums[0];
for(int i = 1; i < n; i++){
minVals[i] = min(minVals[i - 1], nums[i]);
}
stack <int> s;
for(int i = n - 1; i > 0; i--){
int minVal = minVals[i - 1];
int curr = nums[i];
while(!s.empty() && s.top() <= minVal) s.pop();
if(!s.empty() && s.top() < curr) return true;
s.push(nums[i]);
}
return false;
}
};
main(){
vector<int> v = {-1,3,2,0};
Solution ob;
cout << (ob.find132pattern(v));
}
输入
[-1,3,2,0]
输出
1
