C++ में मैक्सिमम विड्थ रैम्प (Maximum Width Ramp)

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, एक रैम्प (i, j) का एक टपल है जिसके लिए i < j और A[i] ≤ A[j]। ऐसे रैम्प की चौड़ाई j - i होती है। हमें A में रैम्प की अधिकतम चौड़ाई खोजनी है। यदि कोई नहीं है, तो 0 लौटाएं।

उदाहरण के लिए, यदि इनपुट [6,0,8,2,1,5] है, तो आउटपुट 4 होगा। यहां अधिकतम चौड़ाई रैम्प (i, j) = (1, 5) पर प्राप्त होता है जहां A[1] = 0 और A[5] = 5।

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

1. एक स्टैक st बनाएं, n := A का आकार, ret := 0

2. i को 0 से n-1 तक: यदि स्टैक खाली है या शीर्ष तत्व > A[i], तो i को पुश करें

3. i को n-1 से ret+1 तक घटाते हुए: जब तक स्टैक खाली नहीं और शीर्ष ≤ A[i], ret अपडेट करें और पॉप करें

4. ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int maxWidthRamp(vector<int>& A) { 
        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; 
    } 
}; 

int main(){ 
    vector<int> v1 = {6,0,8,2,1,5}; 
    Solution ob; 
    cout << (ob.maxWidthRamp(v1)); 
    return 0; 
}

इनपुट

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

आउटपुट

4