สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม ทางลาดคือทูเพิล (i, j) ซึ่ง i
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
สร้างอาร์เรย์ v ตั้งค่า n :=ขนาดของอาร์เรย์ที่กำหนด set ret :=0
กำหนดสแต็ก st
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
หาก st ว่างเปล่าหรือองค์ประกอบบนสุดของสแต็ก> A[i] ให้แทรก i ลงใน st
for i :=n – 1 down to 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
