Viiisit [LeetCode] - 121. Best Time to Buy and Sell Stock

keep learning, keep coding!

Problem - Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the i day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

翻譯蒟蒻

在給定的股票價格陣列中找到最佳的買入和賣出時機，以獲得最大的利潤。每個元素 prices[i] 表示股票在第 i 天的價格。只能進行一次買入和賣出操作，且買入操作必須在賣出操作之前。如果無法獲得任何利潤，則返回 0。

• Example 1:

  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.

• Example 2:

  Input: prices = [7,6,4,3,1]
  Output: 0
  Explanation: In this case, no transactions are done and the max profit = 0.

---

Solution - JavaScript

Solution 1:
想法對，但是超時！
這種暴力解法的時間複雜度是 O(n^2)，在價格數組很大的情況下，可能會導致超時。
(Time Limit Exceeded)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] - prices[i] > max) {
        max = prices[j] - prices[i];
      };
    };
  };
  return max
};

這種暴力解法，使用兩個嵌套的迴圈，依次檢查所有可能的買入和賣出組合，
計算他們之間的利潤，並找出最大的利潤。

Solution 2:
這種方法的時間複雜度是 O(n)，因為只需一次遍歷。
(Runtime - 67ms)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let maxProfit = 0;
  let minPrice = prices[0]
  for (let i = 1; i < prices.length; i++) {
    let profit = prices[i] - minPrice;
    maxProfit = Math.max(maxProfit, profit)
    if (prices[i] < minPrice) {
      minPrice = prices[i]
    }
  };
  return maxProfit
};

改用一個迴圈，同時維護最低價格和最大利潤。
每次迭代時，計算當前價格賣出的利潤，同時更新最低價格和最大利潤。

Solution - Ruby

Solution 1:

def max_profit(prices)
  max_profit = 0
  min_price = prices[0]

  (1...prices.length).each do |i|
    profit = prices[i] - min_price
    max_profit = [max_profit, profit].max
    min_price = prices[i] if prices[i] < min_price
  end

  max_profit
end

• 依照剛剛 JavaScript 的邏輯去想，改用 Ruby 的語法去改寫。

Solution 2:

def max_profit(prices)
  max_profit = 0
  min_price = prices[0]

  prices.each do |price|
    min_price = [min_price, price].min
    max_profit = [max_profit, price - min_price].max
  end

  max_profit
end

這裡活用 Ruby 的語法，以更簡潔的方式去撰寫，
概念上其實與 Solution 1 是一致的，同時更新最小價格和最大利潤。

LeetCode 傳送門 - Best Time to Buy and Sell Stock