使用O(n)从数组获得最大的时间顺​​序下降,最小值和最大值

Question

我编写了一个javascript函数来分析数组中最大的下降.但仍有一个小问题.作为最大值,我总是从我的数组中得到最大值,而不是从我的数据中得到最大值.

示例:数组:[100,90,80,120]

最大的下降将介于100和80之间.因此,max必须为100,并且最小值为80.我的函数始终返回整个数组中的最高值.在我的情况下120

function checkData(data) {
  let max = 0
  let min = 0
  let drop = 0

  for (let i = 0; i < data.length; i++) {
      if (max < data[i]) {
          max = data[i] //?
      } else {
          let tempDrop = max - data[i]
          drop = Math.max(tempDrop, drop)
          min = max - drop
      }
  }
  return [max, min, drop]
}

我想从左到右得到按时间顺序排列的最正确的三角洲

Answer 1

您的循环应该跟踪当前的下降并将其与之前的最大下降进行比较.您可以通过跟踪索引来执行此操作:

function checkData(data) {
  let bestDropStart = 0
  let bestDropEnd = 0
  let bestDrop = 0
  let currentDropStart = 0
  let currentDropEnd = 0
  let currentDrop = 0
  for (let i = 1; i < data.length; i++) {
    if (data[i] < data[i - 1]) {
      // we are dropping
      currentDropEnd = i
      currentDrop = data[currentDropStart] - data[i]
    } else {
      // the current drop ended; check if it's better
      if (currentDrop > bestDrop) {
        bestDrop = currentDrop
        bestDropStart = currentDropStart
        bestDropEnd = currentDropEnd
      }
      // start a new drop
      currentDropStart = currentDropEnd = i
      currentDrop = 0
    }
  }
  // check for a best drop at end of data
  if (currentDrop > bestDrop) {
    bestDrop = currentDrop
    bestDropStart = currentDropStart
    bestDropEnd = currentDropEnd
  }
  // return the best drop data
  return [data[bestDropStart], data[bestDropEnd], bestDrop]
}

console.log(checkData([100, 90, 80, 120]))
console.log(checkData([100, 90, 80, 120, 30]))
console.log(checkData([70, 100, 90, 80]))
console.log(checkData([100, 90, 80, 120, 30, 50]))

您也可以通过保持当前和最佳丢弃的开始和结束值来实现,但我的偏好是明确跟踪索引.这样看起来更清晰(更容易调试和维护).