Maximum Width Ramp ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A of integers, ramp คือคู่ (i, j) ที่ i < j และ A[i] <= A[j] ความกว้าง = j - i ต้องการหาความกว้างสูงสุด

ตัวอย่าง: [6,0,8,2,1,5] → 4 (i=1, j=5: A[1]=0, A[5]=5)

วิธีแก้ปัญหา (Monotonic Stack)

1. สร้าง stack เก็บ index ที่เป็น candidate สำหรับ i (ค่า A[i] ลดลงเรื่อยๆ)
2. วนจากขวาไปซ้าย (j จาก n-1 ถึง 0) หา i ที่ A[i] <= A[j] และ j-i สูงสุด
3. Pop stack เมื่อเจอคู่ที่ตรงเงื่อนไข

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        stack<int> st;
        
        // สร้าง stack ของ candidate i (ค่าลดลง)
        for(int i = 0; i < n; i++) {
            if(st.empty() || A[st.top()] > A[i]) {
                st.push(i);
            }
        }
        
        int ret = 0;
        // วนจากขวาไปซ้าย
        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);
    return 0;
}

อินพุต

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

เอาต์พุต

4