C++-এ k-এর নীচে এবং উপরে একই সংখ্যক উপাদান পেতে সাবলিস্ট মুছে ফেলার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে এবং আরেকটি সংখ্যা k, আমরা তালিকা থেকে সর্বাধিক একবারে যেকোনো সাবলিস্ট সরিয়ে ফেলতে পারি। আমাদের দীর্ঘতম ফলাফলের তালিকার দৈর্ঘ্য খুঁজে বের করতে হবে যেমন k এর থেকে কঠোরভাবে কম এবং k এর থেকে কঠোরভাবে বড় সংখ্যার পরিমাণ একই।

সুতরাং, যদি ইনপুটটি nums =[6, 10, 8, 9, 3, 5], k =6 এর মত হয়, তাহলে আউটপুট হবে 5, যেমন আমরা সাবলিস্ট [9] মুছে ফেলি তাহলে আমরা [6, 10, 8, 3, 5] এবং দুটি সংখ্যা রয়েছে [3, 5] যা 6 থেকে ছোট এবং দুটি সংখ্যা [10, 8] 6 থেকে বড়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সংখ্যা + 1 এর মতো আকারের একটি বিন্যাস সংজ্ঞায়িত করুন এবং 0 দিয়ে পূরণ করুন
• cnt :=0
• আরম্ভ করার জন্য i :=0, যখন i <সংখ্যার আকার, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
  • যদি সংখ্যা[i]
  • (1 দ্বারা cnt বাড়ান)
• অন্যথায় যখন nums[i]> k, তারপর:
  • (cnt 1 কমিয়ে দিন)
• v[i + 1] =cnt

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int solve(vector<int>& nums, int k) {
      vector<int> v(nums.size() + 1, 0);
      int cnt = 0;
      for (int i = 0; i < nums.size(); ++i) {
         if (nums[i] < k)
            ++cnt;
         else if (nums[i] > k)
            --cnt;
         v[i + 1] = cnt;
      }
      if (v.back() == 0) return int(nums.size());
      int delta = v.back();
      map<int, int> m;
      int ans = INT_MAX;
      for (int i = 1; i <= v.size(); ++i) {
         if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) {
            ans = min(ans, i - m[v[i] - v.back()]);
         }
         m[v[i]] = i;
      }
      if (ans == INT_MAX)
         return 0;
      else
         return int(nums.size() - ans);
   }
};
main(){
   Solution ob;
   vector<int> v = {6, 10, 8, 9, 3, 5};
   int k = 6;
   cout << ob.solve(v, k); }

ইনপুট

{6, 10, 8, 9, 3, 5}, 6

আউটপুট

5