Easyarrays
Решить задачу Best Time to Buy and Sell Stock (LeetCode 121)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 121. Максимальная прибыль от одной покупки-продажи (buy перед sell). Один проход: отслеживаем min price и max profit. O(n) время, O(1) память.
def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profitЭквивалентно max subarray на diffs (prices[i] - prices[i-1]) через Kadane. Вариации: 122 (multiple transactions, жадно collect positive diffs), 123 (≤2 transactions, DP), 188 (≤k transactions), 309 (с cooldown), 714 (с fee). Для single transaction это классический one-pass.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.