題目

You are given an array prices where prices[i] is the price of a given stock on the ith 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

Example 1

1
2
3
4
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

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

解釋題目

給你一個 array，叫做 prices，prices 中每個值是一支股票每天的價格，題目要求在其中一天買進，另一天賣出，以獲得最大利益。要注意的是，股票要先買進才能賣出，且同一天只能買或賣，不能買賣同時操作。

思路

  1. 可用雙指針解題，雙指針是左 ( left )、右 ( right ) 指針，一開始會是 left = 0 跟 right = 1
  2. 使用雙指針解題，通常用 while，條件設定是「右指針」走到底結束。
  3. 目的: 要找到最小值 m，找到 m 後，m 後面的數字減去 m 的最大值就是 max_profit
  4. 如何要找到最小值?
    1. prices[right] - prices[left]，如果 > 0，代表 prices[left]，目前是最小值
      1. right 指針繼續往右走，看有沒有更大的 profit
    2. prices[right] - prices[left]，如果 < 0，代表出現比 prices[left] 更小的值，所以透過這樣可以找到最小值 m
      1. 此時，把最小值 m 的位置指派給 left，也就是 left = right

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit(self,prices):
        length = len(prices)
        left = 0
        right = 1
        max_profit = 0
        while right < length:
            profit = prices[right] - prices[left]
            if profit < 0:
                # 找最小值
                left = right
            else:
                max_profit = max(profit, max_profit)
            right = right + 1
        return max_profit