Maximum Width Ramp

Description

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j].  The width of such a ramp is j - i.

Find the maximum width of a ramp in A.  If one doesn't exist, return 0.

 

Example 1:

Input: [6,0,8,2,1,5]
Output: 4
Explanation: 
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: 
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

 

Note:

1. 2 <= A.length <= 50000
2. 0 <= A[i] <= 50000

 

Solution(javascript)

// 双指针可解此题，left, right 指针，一旦找到 A[left] <= A[right], return right -left
// *  O(n)，哦不行，我们还需要选择走那个指针

/** 遍历 O(n^2)
 * @param {number[]} A
 * @return {number}
 */
// const maxWidthRamp = function (A = []) {
//   let max = 0
//   for (let i = 0; i <= A.length - 2; i++) {
//     for (let j = A.length - 1; j >= i + 1; j--) {
//       if (A[j] - A[i] >= 0) {
//         max = Math.max(j - i, max)
//       }
//     }
//   }
//   return max
// }

// 先排序 O(nlog(n))
// const maxWidthRamp = function (A = []) {
//   let max = 0
//   const indexes = A.map((v, index) => index).sort((a, b) => (A[a] === A[b] ? a - b : A[a] - A[b]))
//   let minIndex = indexes[0]
//   for (const index of indexes) {
//     max = Math.max(index - minIndex, max)
//     minIndex = Math.min(index, minIndex)
//   }
//   return max
// }

// Greedy 把最小值先给他存起来，然后从右往左遍历，把他们和这些最小值比较
// O(n)
const maxWidthRamp = function (A = []) {
  let max = 0
  const stack = [0]
  for (let i = 1; i < A.length; i++) {
    if (A[i] < A[stack[stack.length - 1]]) {
      stack.push(i)
    }
  }
  for (let i = A.length - 1; i >= 0; i--) {
    while (A[i] >= A[stack[stack.length - 1]]) {
      max = Math.max(max, i - stack.pop())
    }
  }
  return max
}