Maximum Width Ramp trong C++

Cho mảng A, ramp là cặp (i, j) với i < j và A[i] ≤ A[j]. Độ rộng là j - i. Tìm độ rộng ramp lớn nhất. Nếu không có trả về 0.

Ví dụ: [6,0,8,2,1,5] → 4 (i=1, j=5: A[1]=0 ≤ A[5]=5).

Giải pháp dùng stack đơn điệu:

• Xây stack chỉ số giảm dần theo giá trị A (chỉ push nếu A[i] < đỉnh stack)

• Duyệt từ phải sang trái (i = n-1 xuống ret+1):
  While stack không rỗng và A[stack.top] ≤ A[i]:
  ret = max(ret, i - stack.top), pop stack

• Trả về ret

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int maxWidthRamp(vector<int>& A) {       int n = A.size(), 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)); }

Đầu vào

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

Đầu ra

4