মান লেযিয়ে একটি পূর্ণসংখ্যা অ্যারে A দেওয়া আছে, একটি র্যাম্প হল একটি টাপল (i, j) যেখানে i < j এবং A[i] <= A[j]। এমন একটি র্যাম্পের প্রস্থ j - i। A-তে র্যাম্পের সর্বাধিক প্রস্থ খুঁজে বের করতে হবে। যদি না থাকে, ০ রিটার্ন করুন। ইনপুট [6,0,8,2,1,5] হলে আউটপুট ৪। এখানে সর্বাধিক প্রস্থের র্যাম্প (i, j) = (1, 5)-এ পাওয়া যায়, A[1] = 0 এবং A[5] = 5।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি v অ্যারে তৈরি করুন, n := A.size(), ret := 0
একটি st স্ট্যাক সংজ্ঞায়িত করুন
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
যদি st খালি হয় বা A[st.top()] > A[i] হয়, st-এ i পুশ করুন
i = n-1 থেকে ret+1 পর্যন্ত ডিক্রিমেন্ট করে লুপ চালান
যখন st খালি নয় এবং A[st.top()] <= A[i]
ret := max(ret, i - st.top())
st থেকে পপ করুন
st থেকে পপ করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
