सी ++ में अधिकतम चौड़ाई रैंप

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी A है, एक रैंप एक टपल (i, j) है जिसके लिए i पर प्राप्त किया जाता है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सरणी v बनाएं, n सेट करें:=दिए गए सरणी का आकार, सेट रिट:=0

• स्टैक सेंट को परिभाषित करें

• मेरे लिए 0 से n - 1 की सीमा में

  • अगर सेंट खाली है या स्टैक टॉप एलिमेंट> A[i], तो i को st में डालें

• i के लिए :=n – 1 डाउन टू रिट + 1

  • जबकि सेंट खाली नहीं है और सेंट के ऊपर <=ए[i]

    • रिट :=अधिकतम रिट और (i - सेंट के ऊपर)

    • सेंट से हटाएं

• सेंट से हटाएं

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxWidthRamp(vector<int>& A) {
      vector < pair <int, int> > v;
      int n = A.size();
      int ret = 0;
      stack <int> st;
      for(int i = 0; i < n; i++){
         if(st.empty() || A[st.top()] > A[i]){
            st.push(i);
         }
      }
      for(int i = n - 1; i > ret; i--){
         while(!st.empty() && A[st.top()] <= A[i]){
            ret = max(ret, i - st.top());
            st.pop();
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {6,0,8,2,1,5};
   Solution ob;
   cout << (ob.maxWidthRamp(v1));
}

इनपुट

[6,0,8,2,1,5]

आउटपुट

4