题目

给定一个整数数组 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.

提示：2 <= A.length <= 50000

0 <= A[i] <= 50000

解题思路分析

1、自定义排序；时间复杂度O(nlog(n))，空间复杂度O(n)

type Node struct {   Value int   Index int}func maxWidthRamp(A []int) int {   res := 0   n := len(A)   arr := make([]Node, n)   for i := 0; i < n; i++ {      arr[i] = Node{         Value: A[i],         Index: i,      }   }   sort.Slice(arr, func(i, j int) bool {      if arr[i].Value == arr[j].Value {         return arr[i].Index < arr[j].Index      }      return arr[i].Value < arr[j].Value   })   minIndex := n // 保存当前遇到的最小下标   for i := 0; i < n; i++ {      res = max(res, arr[i].Index-minIndex)      minIndex = min(minIndex, arr[i].Index)   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}func min(a, b int) int {   if a > b {      return b   }   return a}

2、二分查找；时间复杂度O(nlog(n))，空间复杂度O(n)

type Node struct {   Value int   Index int}func maxWidthRamp(A []int) int {   res := 0   n := len(A)   arr := make([]Node, 0) // Value递增数组   arr = append(arr, Node{      Value: A[n-1],      Index: n - 1,   })   for i := n - 2; i >= 0; i-- {      left, right := 0, len(arr)      for left < right {         mid := left + (right-left)/2         if arr[mid].Value < A[i] { // 不满足条件            left = mid + 1         } else {            right = mid         }      }      if left < len(arr) {         index := arr[left].Index         res = max(res, index-i)      } else {         arr = append(arr, Node{            Value: A[i],            Index: i,         })      }   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}

3、单调栈；时间复杂度O(n)，空间复杂度O(n)

func maxWidthRamp(A []int) int {   res := 0   n := len(A)   stack := make([]int, 0) // 递减栈   for i := 0; i < n; i++ {      if len(stack) == 0 || A[stack[len(stack)-1]] > A[i] {         stack = append(stack, i)      }   }   for i := n - 1; i >= 0; i-- {      for len(stack) > 0 && A[stack[len(stack)-1]] <= A[i] {         index := stack[len(stack)-1] // 坡底index能形成的最大宽度         stack = stack[:len(stack)-1]         res = max(res, i-index)      }   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}

4、暴力法；时间复杂度O(n^2)，空间复杂度O(1)

func maxWidthRamp(A []int) int {   res := 0   for i := 0; i < len(A); i++ {      for j := len(A) - 1; j > i+res; j-- {         if A[i] <= A[j] {            res = max(res, j-i)            break         }      }   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}