Когда покупать/продавать акции? Дан массив, содержащий дневную цену акции. Старайтесь найти максимальную прибыль.
Input: [20,10,30,44,26,40,50] Output: 58 Explanation: Buy on day 2 and sell on day 4, profit = 44-10 = 34. Buy on day 5 and sell on day 7, profit = 50-26 = 24.
Мыслительный процесс:
Из предыдущего вопроса Переместить нули мы знаем, что, по крайней мере, мы хотим пройти по входному массиву один раз, поэтому временная сложность будет равна O(n)
. Мы можем использовать дополнительную структуру данных (например, Array/Linked List/Map/Set
), чтобы хранить ежедневную прибыль и суммировать прибыль в конце. Но подождите секунду, разве нас действительно волнует, в какой день мы заработаем, сколько прибыли? Или мы можем просто суммировать общую прибыль, перебирая входной массив?
Решение:
makeProfit(prices) { // Use a constant space O(1) to record total profit. let profit = 0; // While looping through the input array, we calculate the profit and add it to the sum. for(let i = 0; i < prices.length - 1; i++) { profit += Math.max(0, prices[i + 1] - prices[i]); } return profit; };
Ключевые примечания:
- Экономьте место
- Как отследить и рассчитать прибыль от входного массива?
Какой следующий вопрос?
Найти дубликаты — Учитывая массив чисел, вернуть true, если какое-либо число встречается в массиве более одного раза, в противном случае вернуть false. (мысленный процесс и решение)
Перед тем, как ты уйдешь -
Нет лучшего способа поддержать меня, чем подписаться на Medium (Victor Lin). Дайте мне знать, что я должен писать больше!
Знаете ли вы, что вы можете дать до 50 👏, нажав на кнопку 👏? Попробуйте, если вам очень понравилась эта статья!