2023-03-13：给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]，
这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0。
示例 1：
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5。
示例 2：
输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1。
答案2023-03-13：
单调栈，严格来说说递减栈。然后从右往左遍历。
时间复杂度：O(N)。
空间复杂度：O(N)。
这代码用山寨版chatgpt写，不用改代码。
代码用rust编写。代码如下：
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);
}
代码用golang编写。代码如下：
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)
}
}
