ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে রয়েছে, একটি র্যাম্প হল একটি টিপল (i, j) যার জন্য i
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
একটি অ্যারে তৈরি করুন, প্রদত্ত অ্যারের n :=আকার সেট করুন, ret :=0
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
0 থেকে n – 1
যদি st খালি হয় বা স্ট্যাকের উপরের উপাদান> A[i], তাহলে i ঢোকান st
i এর জন্য :=n – 1 ডাউন টু ret + 1
যখন st ফাঁকা নয় এবং st <=A[i>
ret :=ret এর সর্বোচ্চ এবং (i – st এর শীর্ষ)
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
