Привет, друзья, в сегодняшней задаче Leetcode мы будем работать над решением лучшего времени для покупки и продажи акций в javascript.

Вот набор задач

«Вам дан массив prices, где prices[i] — цена данной акции на ith день.

Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.

Возвратите максимальную прибыль, которую вы можете получить от этой транзакции. Если вы не можете получить никакой прибыли, верните 0».

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Во-первых, мы хотим прочитать проблему и убедиться, что понимаем, что они хотят, чтобы мы решили.

Вот что я понимаю

Нам дан массив чисел, где все индексы можно представить как торговые дни недели. Например, понедельник, вторник, среда и т. д. Однако фактическое значение массива — это стоимость акции. Итак, нам нужно выяснить, когда мы можем купить акции, чтобы продать их с наибольшей прибылью. Следует иметь в виду, что мы не можем продать до того, как купим.

Решение с использованием псевдокода

скелет для этой функции будет

function maxProfit(prices) {
}

После того, как мы поймем, что они хотят, чтобы мы сделали. Давайте подумаем, какие шаги мы можем предпринять, чтобы найти решение. Один из лучших способов сделать это для меня — использовать псевдокод. Это помогает мне записывать процесс, не задумываясь о том, как писать какой-либо код.

Для этой задачи нам нужно отслеживать цену покупки акций и прибыль, которую мы получим. Мы можем сделать это, назначив его переменной.

[7, 1, 5, 3, 6, 4] //the array
function maxProfit(prices) {
// Original price
// Profit
}

Теперь, когда у нас есть переменные, которые отслеживают первоначальную цену и прибыль, мы можем начать цикл по массиву. Для этого мы будем использовать цикл for. После того, как мы пройдемся по массиву, мы хотим проверить, есть ли прибыль. Если прибыли нет, мы можем продолжить наш следующий шаг. Который проверяет, меньше ли моя текущая цена покупки, чем моя старая цена. Если это так, мы можем пойти дальше и заменить нашу старую цену на текущую. Мы будем отслеживать нашу прибыль в переменной, которую мы назначили в начале. Затем мы хотим сравнить новую прибыль со старой прибылью. Если наша новая прибыль больше, чем наша старая, мы отслеживаем новую прибыль.

the problem: [7, 1, 5, 3, 6, 4] 
function maxProfit(prices) {
// Original price
// Profit
// Loop through the array and check if it there is profit
  // if there is no profit, continue
  // if there is profit,
     // check if my current purchase price is less than my old price 
       // replace my starting price
   // track our profit
     // computed profit > profit
       // track it
}

Теперь вот как будет выглядеть код

the problem: [7, 1, 5, 3, 6, 4]
function maxProfit(prices) {
// Original price
let buyPrice = price[0]
// Profit
let profit = 0
// Loop through the array and check if it there is profit
for (let i = 0; i < prices.length-1; i++) {
    let tempProfit = prices[i+1]-prices[i];
      if(tempProfit[i] > 0) {
          buyPrice = prices[i];
      }
      if(prices[i+1] - buyPrice > profit) {
            profit = prices[i+1] - buyPrice;
       }
     }
 }
return profit 
}

Теперь давайте посмотрим, проанализируем ли мы нашу пространственную и временную сложность нашего решения сегодня. Для сложности нашего пространства мы создаем только переменную buyPrice. Итак, я считаю, что наша пространственная сложность постоянна, потому что ни одна из наших переменных не растет, и мы только один раз перебираем наш массив.

Space complexity = O(1)
Time complexity = O(N)

Если вам понравилось решение, ставьте лайк и комментируйте свои мысли :)