peak-index-in-a-mountain-array.md

Peak Index in a Mountain Array

Feb 8, 2021 · 2 min read

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

Есть один элемент, который можно назвать пиком. Найти индекс этого элемента.

Задача на LeetCode.

Решение #

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

Сложность — O(n). После этого спросят «а можно ли быстрее?», и ответ разумеется «можно». Задача на бинарный поиск. Попробуем описать мыслительный процесс, который помогает это понять.

Мы понимаем, что есть два тренда: восходящий и нисходящий, и есть ровно один пик, который лежит на стыке. Можно взять любые две соседние точки и задать себе вопрос — какой это тренд? Если восходящий, значит пик где-то справа, если нисходящий — значит слева.

Ровно это свойство и позволяет применить бинарный поиск, по определению.

/**
 * @param {number[]} A
 * @return {number}
 */
var peakIndexInMountainArray = function(A) {
  // границы в пределах
  // которых будем искать ответ
  let start = 0;
  let end = A.length - 1;

  // бинарный поиск двигает
  // start и end друг к другу,
  // сужая количество возможных
  // вариантов для поиска вдвое на каждом шаге
  while (start < end) {
    const middle = Math.floor((start + end) / 2);

    // т.к. минимальная длина 3 (уточнили у интервьюера?) →
    // выход за границу массива не страшен,
    // но в общем случае здесь
    // нужно быть аккуратнее (проверять edge cases):
    // если длина массива 1, то middle будет равен 0,
    // соответственно A[middle + 1] — за границей массива

    if (A[middle] < A[middle + 1]) {
      // middle оказался в восходящем тренде,
      // соответственно надо продолжать поиск справа,
      // при этом раз A[middle + 1] оказался
      // больше — значит middle + 1 ближе к пику
      start = middle + 1;
    } else {
      // middle оказался в нисходящем тренде,
      // соответственно надо продолжать поиск слева,
      // при этом раз A[middle] оказался
      // больше — значит middle ближе к пику
      end = middle;
    }
  }
  // на данном этапе A[start] > A[end]
  // и отличаются на единицу,
  // т.е. мы нашли самое начало
  // нисходящего тренда — это и есть пик
  return start;
};

Сложность O(log N). Мы уменьшаем количество возможных вариантов для проверки вдвое на каждом шаге, а значит в худшем случае нужно сделать log N итераций цикла.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.