132 รูปแบบใน C++

สมมติว่าเรามีลำดับของจำนวนเต็ม n a1, a2, ..., an, รูปแบบ 132 เป็นลำดับรองลงมา ai, aj, ak เช่นว่า i

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums ถ้า n เป็น 0 ให้คืนค่าเท็จ

• กำหนดอาร์เรย์ที่เรียกว่า minVals ขนาด n ตั้งค่า minVals[0] :=nums[0]

• สำหรับผมอยู่ในช่วง 1 ถึง n – 1

  • minVals[i] :=ขั้นต่ำของ minVals[i - 1] และ nums[i]

• สร้างสแต็ก st

• สำหรับผมอยู่ในช่วง n – 1 เหลือ 1

  • minVal :=minVals[i – 1]

  • สกุลเงิน :=nums[j]

  • ในขณะที่ st ไม่ว่างเปล่าและด้านบนของสแต็กคือ <=minVal

    • ลบออกจาก stack st

  • ถ้า st ไม่ว่างและอยู่ด้านบนของ stack

  • ใส่ nums[i] ลงใน s

• คืนค่าเท็จ

ตัวอย่าง (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