LeetCode 刷題紀錄｜121. Best Time to Buy and Sell Stock (Easy)

Roy Wang

Published in

RoyWannago

3 min readNov 13, 2020

看到這題名字可能會想到 Dynamic Programming，但這題是 Stock 系列的忙內（？），解法不複雜～

121. Best Time to Buy and Sell Stock

Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Question

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [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. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: 
In this case, no transaction is done, i.e. max profit = 0.

題目給的 Array 裡面每一個數字都代表當天的股價，請你算出哪天買入哪天賣出會得到最大收益，輸出只需要給收益的數字。要注意要先買進才能賣出，所以 Array 不能亂動～如果會賠錢就都不要買賣

Answers

Solutions:

Naive: 2 loops
One pass with tracking the min price

1: Brute Force

暴力解就是去抓每一個買入買出的收益，去看哪個最大

[7,1,5,3,6,4]

i = 0, 買入prices[i]: 7, 賣出 prices[j]: 1 (-6), 5(-2), 3(4), 6(-1), 4(-3),
最大收益=4

i = 1, 買入prices[i]: 1, 賣出 prices[j]: 5(4), 3(2), 6(5) 最大收益為 5, 4(3),
最大收益仍為 5

i = 2,買入prices[i]: 5, 賣出 prices[j]: 3(-2), 6(1), 4(-1) 最大收益仍為 5

i = 3, 買入prices[i]: 3, 賣出 prices[j]: 6(-3), 4(1), 最大收益仍為 5

i = 4, 最後買入prices[i]: 6, 賣出 prices[j]: 4(-2), 最大收益仍為 5

Time complexity: O(n²)
Space complexity: O(1)

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

2: One Pass

投過記住歷史最低買入價的方式，減少成只需要一個loop就好

[7,1,5,3,6,4]

i = 0, prices[i] = 7, minPrice = 7, prices[i] — minPrice = 0, maxProfit = 0

i = 1, prices[i] = 1, minPrice = 1, prices[i] — minPrice = 0, maxProfit = 0

i = 2, prices[i] = 5, minPrice = 1, prices[i] — minPrice = 4, maxProfit = 4

i = 3, prices[i] = 3, minPrice = 1, prices[i] — minPrice = 2, maxProfit = 4

i = 4, prices[i] = 6, minPrice = 1, prices[i] — minPrice = 5, maxProfit = 5

i = 5, prices[i] = 4, minPrice = 1, prices[i] — minPrice = 3, maxProfit = 5

答案：5

Time complexity: O(n)
Space complexity: O(1)

Javascript:

var maxProfit = function (prices) {
  let maxProfit = 0;
  let minPrice = Infinity;  for (let i = 0; i < prices.length; i++) {
    minPrice = Math.min(minPrice, prices[i])
    maxProfit = Math.max(maxProfit, (prices[i] - minPrice))
  }  return maxProfit;
};

Python:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprice = float('inf')
        maxprofit = 0
        
        for num in prices:
            minprice = min(minprice, num)
            maxprofit = max(maxprofit, num - minprice)
                
        return maxprofit

新手上路，如果有寫錯的地方歡迎大力糾正，歡迎留言討論或是到我的Socials找我~謝謝觀看！

About Roy

Social Media
Facebook — RoyWannago
Twitter — @roywannago
Instagram — @royflwdesign
Website — roywannago.com

LeetCode 刷題紀錄 ｜121. Best Time to Buy and Sell Stock (Easy)