Эта статья была включена в серию Github «Алгоритм обучения Xiaobai»:GitHub.com/VIP камень/Али…
Сегодня Ant Group (Alipay) официально зарегистрирована.Нет никаких сомнений в том, что этот шаг создал большое количество богатых людей.Однако, как аутсайдеры, мы можем только позавидовать. Очевидно, вы можете пройти тест на удачу, чтобы поесть, мы должны полагаться на силу, вы думаете, что это неправильно?
Но опять же, люди, которые могут попасть в муравьев, тоже хорошие люди, поэтому давайте поторопимся и повысим свои навыки, чтобы мы могли подготовиться к следующему «муравью».
Сегодняшний вопрос более интересен, он про "покупку и продажу акций", тема следующая.
Описание темы
Дан массив, i-й элемент которого представляет собой цену данной акции в i-й день. Если вам разрешено совершить не более одной сделки (т. е. купить и продать акции один раз), разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить.
Примечание. Вы не можете продать акцию до ее покупки.
Пример 1:
Ввод: [7,1,5,3,6,4]
Выход: 5
Объяснение: покупка во 2-й день (цена акции = 1), продажа в 5-й день (цена акции = 6), максимальная прибыль = 6-1 = 5. Обратите внимание, что прибыль не может быть 7-1=6, потому что цена продажи должна быть больше цены покупки, в то же время нельзя продать акцию до покупки.
Пример 2:
Ввод: [7,6,4,3,1]
вывод: 0
Объяснение: В этом случае сделка не завершена, поэтому максимальная прибыль равна 0.
Источник: LeetCode
Меч относится к предложению 64:Ли ТСО's-talent.com/problems/so…Сложность: средняя
буквенный код 121:Lee TCO's-talent.com/problems/не голоден…Сложность: легко
Идеи решения проблем
По смыслу названия мы знаем, что у нас есть только одна возможность торговать, то есть купить один раз и продать снова, но в то же время мы должны обеспечить максимальную прибыль. Тогда наш инстинкт состоит в том, чтобы купить по самой низкой цене и продать по самой высокой цене, как показано на следующем рисунке:
Но проблема в том, что мы должны убедиться, что самая высокая цена идет после самой низкой цены, потому что мы должны купить акции, прежде чем мы сможем их продать, а не наоборот, что усложняет проблему.
Но в этот момент мы подумали о самом прямом и глупом методе, который состоит в том, чтобы использоватьВ методе грубой силы мы используем двухслойный цикл, покупаем в каждом узле по очереди, а затем продаем во всех последующих узлах, чтобы вычислить разницу (доход) между узлами, если разница больше, чем текущий самый высокий return, Просто установите это значение на текущую максимальную прибыль, чтобы после завершения цикла мы могли получить максимальную прибыль. Как показано ниже:
Метод 1: Закон о насилии
С приведенной выше идеей давайте реализуем ее с помощью кода:
class Solution {
public int maxProfit(int[] prices) {
int mp = 0; // 最高收益
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int item = prices[j] - prices[i];
if (item > mp) mp = item;
}
}
return mp;
}
}
Видно, что код по-прежнему очень простой, но не стоит слишком волноваться, давайте посмотрим, как он работает на leetcode:
Анализ сложности
- Временная сложность: O(n^2), цикл выполняется n(n-1)/2 раза.
- Пространственная сложность: O(1), с использованием только константно-битовых переменных.
Это была действительно жестокая операция, и в итоге удалось победить 5%! Если вы используете этот код для интервью, считается, что вы можете только вернуться и дождаться уведомления. Есть ли способ лучше? Ответ — да, продолжайте читать.
Способ 2: пройти один раз
Для решения этой задачи мы можем использовать цикл, чтобы достичь, сначала взгляните на следующую линейную диаграмму:
На изображении выше мы видим, что мыНа самом деле в каждом узле выполняются только две вещи (кроме первого узла, который можно только купить, но не продать), это две вещи: купить или продать. Тогда мы можем использовать цикл для вычисления максимальной прибыли,Нам нужно только сделать следующие два суждения для каждого узла по очереди:
- Определить, является ли текущий узел относительно наименьшей ценой, если да, установить его как наименьшую цену (то есть купить);
- Если текущий узел не является самой низкой ценой, то мы продадим его, а затем рассчитаем прибыль от продажи (текущий узел минус относительная самая низкая цена), если прибыль от продажи больше, чем текущая максимальная прибыль, установите это значение к максимальной прибыли.
Таким образом, самая высокая прибыль выходит после завершения цикла.Код реализации выглядит следующим образом:
class Solution {
public int maxProfit(int prices[]) {
if (prices == null || prices.length == 0) return 0;
int mp = 0; // 最高收益
int min = prices[0]; // 最低价
for (int i = 1; i < prices.length; i++) {
if (prices[i] < min) {
// 设定相对最低价
min = prices[i];
} else if (mp < (prices[i] - min)) {
// 设定最高盈利
mp = prices[i] - min;
}
}
return mp;
}
}
Результат приведенного выше кода в leetcode показан на следующем рисунке:
Анализ сложности
- Временная сложность: O(n), нужно пройти только один раз.
- Пространственная сложность: O(1), используются только постоянные переменные.
Из результатов выполнения выше видно, что этот код относительно идеален, так что интервьюер поставит вам большой палец вверх.
Суммировать
В этой статье мы рассчитали самую высокую доходность одной (одной покупки и продажи) акции.В начале мы использовали самый простой и грубый метод перебора грубой силы и использовали два слоя циклов для вычитания по очереди, чтобы найти самую высокую доходность value, но this Эффективность выполнения этого метода слишком низкая.
Затем мы посмотрели на линейный график и обнаружили, что для нахождения максимального возвращаемого значения требуется всего один цикл. Нам нужно только сделать два суждения в каждом узле. Во-первых, решить, является ли этот узел относительным минимальным значением. Если да, запишите его; если нет, подсчитайте, являются ли это значение и относительное минимальное значение текущим самым высоким доходом. , затем запишите Это. Тогда за один цикл мы можем получить наибольшую прибыль, и эффективность исполнения также очень высока.
Вы научились этому? Если есть что-то, что вы не понимаете, или лучший способ, оставьте сообщение в области комментариев ~
Благосостояние в конце статьи: Поиск общедоступной учетной записи «Китайское сообщество Java», чтобы отправить «интервью», чтобы получить последние материалы интервью.