132 Mẫu trong C ++

Giả sử chúng ta có một dãy n số nguyên a1, a2, ..., an, mẫu 132 là dãy con ai, aj, ak sao cho i

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums, nếu n là 0 thì trả về false

• xác định một mảng được gọi là minVals có kích thước n, đặt minVals [0]:=nums [0]

• cho tôi trong phạm vi từ 1 đến n - 1

  • minVals [i]:=tối thiểu là minVals [i - 1] và nums [i]

• tạo ngăn xếp

• cho tôi trong phạm vi n - 1 xuống 1

  • minVal:=minVals [i - 1]

  • curr:=nums [j]

  • trong khi st không trống và đỉnh của ngăn xếp là <=minVal

    • xóa khỏi ngăn xếp st

  • nếu st không trống và trên cùng của ngăn xếp

  • chèn nums [i] vào s

• trả về false

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

->

#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));
}

Đầu vào

[-1,3,2,0]

Đầu ra

1