C++ में प्रत्येक k आकार के सन्निकट सबअरे का अधिकतम मान ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास n तत्वों की एक सरणी और एक मान k है। हमें आकार k के प्रत्येक सन्निकट सबअरे के लिए अधिकतम मान ज्ञात करना है।

उदाहरण के लिए, यदि इनपुट arr = [3,4,6,2,8], k = 3 है, तो आउटपुट होगा: आकार 3 के सन्निकट सबअरे [3,4,6], [4,6,2], [6,2,8] हैं, इसलिए अधिकतम तत्व 6, 6 और 8 हैं।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम डीक्यू (deque) आधारित स्लाइडिंग विंडो एल्गोरिदम का उपयोग करते हैं:

• आकार k का एक डीक्यू Qi परिभाषित करें
• i := 0 से k-1 तक:
  • जब तक Qi खाली नहीं है और arr[i] >= arr[Qi का अंतिम तत्व]:
    • Qi से अंतिम तत्व हटाएं
  • i को Qi के अंत में डालें
• i := k से arr के आकार तक:
  • arr[Qi का पहला तत्व] प्रदर्शित करें
  • जब तक Qi खाली नहीं है और Qi का पहला तत्व <= i - k:
    • Qi से पहला तत्व हटाएं
  • जब तक Qi खाली नहीं है और arr[i] >= arr[Qi का अंतिम तत्व]:
    • Qi से अंतिम तत्व हटाएं
  • i को Qi के अंत में डालें
• arr[Qi का पहला तत्व] प्रदर्शित करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <iostream> #include <vector> #include <deque> using namespace std; int main(){    vector<int> arr = {3,4,6,2,8};    int k = 3;    deque<int> Qi(k);    int i;    for (i = 0; i < k; ++i){       while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])          Qi.pop_back();          Qi.push_back(i);      }      for ( ; i < arr.size(); ++i){         cout << arr[Qi.front()] << " ";         while ( (!Qi.empty()) && Qi.front() <= i - k)             Qi.pop_front();         while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])             Qi.pop_back();         Qi.push_back(i);     }     cout << arr[Qi.front()] << endl; } 

इनपुट

{3,4,6,2,8}, 3

आउटपुट

6 6 8