132 C ++模式

假设我们有一个由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

• 定义一个大小为n的名为minVals的数组，设置minVals [0]：= nums [0]

• 对于I范围从1到n – 1

• minVals [i]：= minVals [i-1]和nums [i]的最小值

• 创建堆栈st

• 因为我的范围是n – 1至1

• 从堆栈st删除

• minVal：= minVals [i – 1]

• curr：= nums [j]

• 当st不为空并且栈顶为<= minVal

• 如果st不为空并且栈顶<curr，则返回true

• 在s中插入nums [i]

• 返回假

范例（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