数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 中的 132 模式
假设我们有一系列 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 := num 的大小，如果 n 为 0，则返回 false
定义一个名为 minVals 的数组，大小为 n，设置 minVals[0] := num[0]
对于范围 1 到 n - 1 中的 I
minVals[i] := minVals[i - 1] 和 num[i] 的最小值
创建栈 st
对于范围 n - 1 到 1 中的 I
minVal := minVals[i - 1]
curr := num[j]
while st 非空且栈顶 <= minVal
从栈 st 中删除
如果 st 非空且栈顶 < curr，则返回 true
将 num[i] 插入 st
返回 false
示例 (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
更新时间：2020 年 4 月 29 日
330 次查看
广告