132C++のパターン

n個の整数a1、a2、...、anのシーケンスがあるとします。132パターンは、i

これを解決するには、次の手順に従います-

• n：=numsのサイズ。nが0の場合、falseを返します

• サイズnのminValsという配列を定義し、minVals [0]：=nums [0]

  を設定します。

• 1からn–1の範囲のIの場合

  • minVals [i]：=最小のminVals[i-1]とnums[i]

• スタックstを作成

• n –1から1までの範囲のIの場合

  • minVal：=minVals [i – 1]

  • curr：=nums [j]

  • stが空ではなく、スタックの最上位が<=minVal

    である場合

    • スタックstから削除

  • stが空でなく、スタックの最上位

  • nums[i]をs

    に挿入します

• 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