Эта статья является частью серии статей Натана Томаса, разработчика программного обеспечения полного стека, работающего в Сан-Франциско, Калифорния. Среди других его недавних статей — Создание собственного биткойн-узла и Подмассив максимального продукта.
Введение
Если вы ищете краткое руководство по оптимальному решению проблемы LeetCode Лучшее время для покупки и продажи акций, добро пожаловать. 🔥
Этот вопрос входит в Список вызовов кода для слепых 75 LeetCode — группу вопросов, составленную техническим руководителем Facebook, которая рекламируется как отличный способ подготовиться к собеседованию.
Не корите себя слишком сильно, если вы здесь, потому что вам пришлось нелегко. У всех иногда возникают трудности с кодированием.
С учетом сказанного, давайте приступим к делу, чтобы вы могли получить свое решение.
Первоначальная настройка 🏗
Прежде чем писать хоть одну строчку кода, мы должны попытаться понять все правила задачи (см.: Техники решения проблем Поля):
- Нам будет предоставлен список
prices, где каждая цена — это стоимость акции вiдень. - Мы хотим максимизировать нашу прибыль, выбрав одиндень для покупки акций и один день для их продажи.
- День, когда мы продаем акции, должен быть позже дня, когда мы их покупаем.
- Мы должны вернуть максимально возможную прибыль
- Если прибыль невозможна, мы должны вернуть
0
Этого достаточно для того, чтобы мы начали. 🔥
Я буду использовать Python для ответа на этот вопрос, поскольку он немного похож на универсальный язык — предпочитаете ли вы JavaScript, Java, Golang, C или что-то еще, каждый может «отчасти» читать Python.
Я также не буду говорить о «менее оптимальных» решениях. Вы пришли сюда за ответом, верно? Я собираюсь убедиться, что вы получите хороший.
Приступим к делу.
Построение наших переменных
Первое, что нам нужно сделать, это написать несколько переменных для отслеживания max_profit и lowest_price_seen. Мы можем написать их внутри функции следующим образом:
Мы можем инициализировать переменную max_profit значением 0, так как значение по умолчанию (если оно никогда не обновлялось) будет возвращено. Помните, как в наборе правил сказано возвращать 0, если прибыль невозможна?
Теперь мы рассмотрели эту часть. ✅
Кроме того, инициализация lowest_price_seen первой ценой в списке prices дает нам отправную точку для сравнения всего остального. Нам просто нужно убедиться, что наш цикл начинается с индекса 1, чтобы компенсировать это.
Создаем наш цикл 🔁
Следующее, что нам нужно сделать, это написать цикл for, который выполняет итерацию по нашим ценам и выполняет некоторые сравнения, чтобы проверить, можем ли мы (для каждой новой цены) получить лучший max_profit с его помощью или же он ниже нашего текущего lowest_price_seen.
Вот как это выглядит в виде кода:
Это выглядит причудливо, но это действительно просто.
Все, что мы делаем здесь, это начинаем с индекса 1 (как мы говорили в разделе выше), вытягивая каждый новый price по индексу, назначая max_profit в зависимости от того, что является максимальным между его текущим значением или новым price — lowest_price_seen, а затем также обновление lowest_price_seen впоследствии (для будущих итераций), чтобы оно было минимальным между lowest_price_seen или price.
Наконец, мы возвращаем max_profit после того, как наш цикл завершится, как мы и говорили. Если прибыль не была доступна во время выполнения цикла, это все равно будет 0 от значения, с которым мы его инициализировали.
Этот алгоритм работает с временной сложностью O(n) (проходя один раз через наш for цикл) с пространственной сложностью O(1) (поскольку у нас всего пара переменных) и дает нам нужный ответ!
Заключение
Ну вот. 👏🏻
Надеюсь, вы узнали что-то такое же, как мне понравилось писать для вас эту статью.
Следите за остальными статьями Слепые 75 проблем с программированием от меня. Я собираюсь решать их и публиковать по ходу дела.
Кроме того, не стесняйтесь обращаться ко мне по любой из приведенных ниже ссылок, если вы хотите поговорить о кодировании, крутых технологиях или о чем-то еще (мне очень, очень нравятся рекомендации книг).
Спасибо за прочтение. 🔥
Натан
