1. Задача
Дан ряд чисел, например очки в игре: [4, 9, 2, 7]. Какое из них самое большое? Ты видишь ответ сразу. А компьютер за один раз смотрит только в одну коробку и окинуть взглядом весь ряд не может. Как ему найти самое большое число?
2. Идея: держи лучшее пока
Вот приём, который пригодится тебе ещё много раз. Пройди по списку один раз и держи в коробке лучшее пока, то есть самое большое число из тех, что ты уже видел.
Сначала считай самым большим первое число. Потом смотри на каждое следующее. Если оно больше числа в коробке, положи в коробку его. Когда список закончится, в коробке будет ответ.
Проследим на [4, 9, 2, 7]: в коробке сначала 4 → видим 9, это больше, в коробке теперь 9 → видим 2, это меньше 9, ничего не меняем → видим 7, тоже меньше 9 → ответ 9.
4. Где это встречается
«Самый высокий счёт», «самый свежий заказ», «ближайший водитель», «самый дешёвый вариант»: всё это тот же один проход, в котором ты держишь лучшее пока. Замени «больше» на «меньше», и найдёшь самое маленькое. Подставь любое другое правило сравнения, и найдёшь лучшее по этому правилу. Этот маленький приём встречается повсюду.
На LeetCode
Задачи, где за один проход по массиву нужно найти самое большое, самое маленькое или лучшее значение. Держи лучшее на данный момент в переменной и сравнивай с ним каждый новый элемент.
Сначала найди самую большую кучку, потом сравни с ней каждого ребёнка.
Считай текущую серию единиц и запоминай самую длинную из встреченных.
Сложи строку каждого клиента и оставь самую большую сумму.
За один проход храни самую низкую цену на данный момент и самую большую прибыль.
Напиши сам
В редакторе тебя ждёт largest(nums) с пометкой // TODO. Заведи переменную для лучшего пока и положи в неё первое число списка. Пройди циклом по остальным числам и заменяй лучшее каждый раз, когда встретишь число больше. В конце верни лучшее.
Начинай именно с первого числа. В тестах есть список [-4, -9, -2]. Если начать с 0, ни одно число в нём не окажется больше нуля, и функция вернёт 0, хотя такого числа в списке нет. Правильный ответ: -2.
Ещё в тестах есть список из одного числа (ответ: это число) и пустой список. В пустом списке самого большого числа нет, поэтому верни null (в Python это None). Пустой список это «крайний случай». Тебе нужно заранее решить, что делать, когда сравнивать нечего, чтобы программа не упала с ошибкой.
Практика
Find the biggest number
largest(nums) -> the biggest number, or null if nums is empty
// Step 07: find the biggest number. You write the whole function.
//
// largest(nums)
// nums: number[]
// returns the biggest number, or null if nums is empty.
export function largest(nums) {
// TODO: keep the best-so-far while walking nums; return it (null if empty)
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.