Получите наибольшее хронологическое падение, минимальное и максимальное из массива с O (n)

Question

Я написал функцию javascript для анализа самого большого падения в массиве.Но одна маленькая проблема все еще там.В качестве максимального значения я всегда получаю максимальное значение из массива отверстий, а не из моего падения.

Пример: Массив: [100,90,80,120]

Самое большое падение будет между 100и 80. Таким образом, max должно быть 100, а min 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 dropInd = 1,
  	mx = data.reduce((arr,val, ind) => {
 if(ind && val > data[ind-1])dropInd++;  	      
 arr[dropInd] = arr[dropInd] || {max:val};
 arr[dropInd].min = val;
 arr[dropInd].drop = arr[dropInd].max - val;
 return arr;
}, []) //after reduce, islands are created based on 'dropInd'  
  .sort((v1,v2)=>v2.drop - v1.drop) //sort by drop descending
  [0]; //the first value now contains the maximum drop  

  return [mx.max,mx.min,mx.drop];
}



console.log(checkData([100, 90, 80, 120]));
console.log(checkData([100, 90, 80, 120, 200, 100 ,90]));
console.log(checkData([200,100, 90, 80, 120,  100 ,90]));
console.log(checkData([200,120,190, 90, 80, 120,  100 ,90]));

Answer 2

Ваш цикл должен отслеживать текущее падение и сравнивать его с предыдущим наибольшим падением.Вы можете сделать это, отслеживая индексы:

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]))

Вы также можете сделать это, просто сохранив начальные и конечные значения для текущего и лучшего отбрасывания, но я бы предпочел явно отслеживать индексы.Мне это кажется более понятным (легче отлаживать и поддерживать).

Answer 3

Похоже, вы хотите, чтобы возвращаемые значения max и min были такими же, которые использовались при расчете наибольшего падения, а не общего значения max и min.В этом случае просто добавьте дополнительную переменную, чтобы сохранить их, когда drop обновляется.Замените

drop = Math.max(tempDrop, drop)

на оператор if (псевдокод):

if current_drop is greater than stored_drop:
  stored_drop = current_drop
  stored_max_min = current max and min

, затем верните дополнительные сохраненные значения max и min.

Answer 4

Вам необходимо выполнить итерацию массива один раз (O(n)) и сохранить текущий счетчик минимальных и максимальных значений и:

1. Сбрасывать его каждый раз, когда значение увеличивается по сравнению с предыдущим значением
2. Но запишите их, если разница больше, чем ранее отмеченные значения

function checkData(array) {
  var currentmax = array[0];
  var currentmin = array[0];
  var overallmax = array[0];
  var overallmin = array[0];
  var i;
  for (i = 1; i < array.length; i++) {
    if (array[i] <= array[i - 1]) {
      // value is same or decreased
      currentmin = array[i];
    } else {
      // check if previous iteration was the largest
      if (currentmax - currentmin > overallmax - overallmin) {
        overallmax = currentmax;
        overallmin = currentmin;
      }
      // restart
      currentmax = array[i];
      currentmin = array[i];
    }
  }
  // check if last iteration was the largest
  if (currentmax - currentmin > overallmax - overallmin) {
    overallmax = currentmax;
    overallmin = currentmin;
  }

  return [overallmax, overallmin, overallmax - overallmin];
}
console.log(checkData([100, 90, 80, 120]));
console.log(checkData([100, 90, 80, 120, 200, 100, 90]));
console.log(checkData([10, 100, 50, 50, 10, 100, 50, 50, 1]));

Answer 5

Вам необходимо отслеживать две вещи:

• Максимальное значение, которое у вас есть до элемента i.
• Минимальное значение, которое вы имеете от элемента i в конец списка.

Тогда вам просто нужно найти каплю для каждого индекса и выбрать, какой из них самый большой.

Вот код:

function maxDrop (data) {
  if (!data || data.length === 0) {
    return;
  }
  const max = [];
  const min = [];
  for (let i = 0; i < data.length; i++) {
    const left = data.slice(0, i);
    const right = data.slice(i, data.length);
    max.push(Math.max.apply(null, left));
    min.push(Math.min.apply(null, right));
  }
  let maxDrop = max[0] - min[0];
  let maxValue = max[0];
  let minValue = min[0];
  for (let j = 0; j < data.length; j++) {
    const drop = max[j] - min[j];
    if (maxDrop < drop) {
      maxDrop = drop;
      maxValue = max[j];
      minValue = min[j];
    }
  }
  return [maxValue, minValue, maxDrop];
}

console.log(maxDrop([100,90,80,120]))
console.log(maxDrop([100,110,120,300,200,70,60,50,90,400]))
console.log(maxDrop([100,90,80,120,30]))

Answer 6

Это работает точно так, как задумано (согласно ожидаемому результату), как показано в следующем фрагменте кода.

Проблема должна заключаться в том, как вы отправляете свои данные в виде массива.

alert(checkData([100, 90, 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)
      min = max - drop
    }
  }
  return [max, min, drop]
}

// Output : 120, 80, 20

Однако, если вы ищете, это Макс, Мин, а затем самая большая разница, то есть между максимумом и минимумом, который в вашемприведенный пример будет 40, тогда вы можете просто сделать это.

alert(checkData([100, 90, 80, 120]));

function checkData(data) {

  let max = data.reduce(function(a, b) {
    return Math.max(a, b);
  });
  let min = data.reduce(function(a, b) {
    return Math.min(a, b);
  });

  let drop = max-min;

  return [max, min, drop];
  
}

// Output : 120, 80, 40

Я упоминаю об этом только потому, что не знаю, почему вы сказали, что ожидаете наибольшую разницу, равную 20, при 100 и 80, когда у вас есть120 и 80 в одном и том же массиве, что означает наибольшую разницу в 40.