Giả sử chúng ta có một mảng A gồm các số nguyên, một đoạn đường nối là một bộ (i, j) mà i
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Tạo một mảng v, đặt n:=kích thước của mảng đã cho, đặt ret:=0
-
xác định một ngăn xếp
-
cho tôi trong phạm vi từ 0 đến n - 1
-
nếu st trống hoặc phần tử trên cùng của ngăn xếp> A [i], thì hãy chèn i vào st
-
-
for i:=n - 1 xuống ret + 1
-
trong khi st không trống và đầu st <=A [i]
-
ret:=max of ret và (i - top of st)
-
xóa khỏi st
-
-
-
xóa khỏi st
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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)); }
Đầu vào
[6,0,8,2,1,5]
Đầu ra
4