สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องตรวจสอบว่ามีแฝดสาม (i, j, k) ที่ i

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 12, 1, 4, 4] ผลลัพธ์จะเป็น True เนื่องจาก [2, 12, 4] ตรงกับเกณฑ์เพราะ 2 <4 <12

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

• n :=ขนาดของ nums

• กำหนดอาร์เรย์ด้านซ้ายของขนาด n

• ซ้าย[0] :=nums[0]

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

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

• กำหนดหนึ่งสแต็ก st

• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=1 อัปเดต (ลด i โดย 1) ทำ -

  • x :=left[i - 1]

  • ในขณะที่ st ไม่ว่างและอยู่ด้านบนของ st <=x ทำ −

    • ป๊อปจากเซนต์

  • ถ้า st ไม่ว่างเปล่าและ x ด้านบนของ st แล้ว −

    • คืนความจริง

  • ดัน nums[i] เข้า st

• คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(vector<int>& nums) {
      int n = nums.size();
      vector<int> left(n);
      left[0] = nums[0];
      for (int i = 1; i < n; i++) {
         left[i] = min(nums[i], left[i - 1]);
      }
      stack<int> st;
      for (int i = n - 1; i >= 1; i--) {
         int x = left[i - 1];
         while (!st.empty() && st.top() <= x)
            st.pop();
         if (!st.empty() && x < nums[i] && nums[i] > st.top())
            return true;
         st.push(nums[i]);
      }
      return false;
   }
};
bool solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
int main(){
   vector<int> v = {2, 12, 1, 4, 4};
   cout << solve(v);
}

อินพุต

{2, 12, 1, 4, 4}

ผลลัพธ์

1