2023-03-13：给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]，这样的坡的

福大大架构师每日一题

发布于 2023-06-08 14:54:49

21600

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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](https://chatgpt.zcorky.com/)写，不用改代码。

代码用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)
  }
}