Chương trình tìm bộ ba nums [i]

Giả sử chúng ta có một danh sách các số được gọi là nums, chúng ta phải kiểm tra xem có các bộ ba (i, j, k) sao cho i

Vì vậy, nếu đầu vào là nums =[2, 12, 1, 4, 4], thì đầu ra sẽ là True, vì [2, 12, 4] khớp với tiêu chí vì 2 <4 <12.

Để 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

• Xác định một mảng bên trái có kích thước n

• left [0]:=nums [0]

• để khởi tạo i:=1, khi i

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

• Xác định một ngăn xếp

• để khởi tạo i:=n - 1, khi i> =1, cập nhật (giảm i đi 1), thực hiện -

  • x:=left [i - 1]

  • trong khi st không trống và đầu st <=x, do -

    • bật từ st

  • nếu st không trống và x top of st, thì -

    • trả về true

  • đẩy nums [i] vào st

• trả về false

Ví dụ

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

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

Đầu vào

{2, 12, 1, 4, 4}

Đầu ra

1