fn max_width_ramp(arr: &[i32]) -> usize {
    let n = arr.len();
    // 栈中只放下标
    let mut stack = vec![0; n];
    // 栈的大小
    let mut r = 0;
    for i in 0..n {
        if r == 0 || arr[stack[r - 1]] > arr[i] {
            stack[r] = i;
            r += 1;
        }
    }
    let mut ans = 0;
    // 从右往左遍历
    // j = n - 1
    for j in (0..n).rev() {
        while r != 0 && arr[stack[r - 1]] <= arr[j] {
            let i = stack[r - 1];
            r -= 1;
            ans = ans.max(j - i);
        }
    }
    ans
}

fn main() {
    let arr = [6, 0, 8, 2, 1, 5];
    let ans = max_width_ramp(&arr);
    println!("{}", ans);

    let arr = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1];
    let ans = max_width_ramp(&arr);
    println!("{}", ans);
}

package main

import "fmt"

func maxWidthRamp(arr []int) int {
	n := len(arr)
	// 栈中只放下标
	stack := make([]int, n)
	// 栈的大小
	r := 0
	for i := 0; i < n; i++ {
		if r == 0 || arr[stack[r-1]] > arr[i] {
			stack[r] = i
			r++
		}
	}
	ans := 0
	// 从右往左遍历
	// j = n - 1
	for j := n - 1; j >= 0; j-- {
		for r != 0 && arr[stack[r-1]] <= arr[j] {
			i := stack[r-1]
			r--
			ans = max(ans, j-i)
		}
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	if true {
		arr := []int{6, 0, 8, 2, 1, 5}
		ans := maxWidthRamp(arr)
		fmt.Println(ans)
	}
	if true {
		arr := []int{9, 8, 1, 0, 1, 9, 4, 0, 4, 1}
		ans := maxWidthRamp(arr)
		fmt.Println(ans)
	}
}