Chris's Lab

If you obey all the rules,you miss all the fun.

0%

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

發表於 分類於 ， ， Disqus：
究竟何時才是買賣股票的最好時機呢?

前言

　　究竟何時才是買賣股票的最好時機呢? 這題邏輯很生活化，就是把一個陣列內所有的價格遍歷完，低買高賣後把最大的差價回傳出來，這題使用了單迴圈遍歷陣列裡所有的價格，遍歷裡也是常數的時間操作，時間複雜度推算可以達到 O(n)，這篇有 Java 和 Python 的寫法。

題目

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.

給你一個價格陣列 prices ，prices[i] 是取得一個股票在第 i 天的價格。
你想要最大化你的利潤，藉著選擇一天去買一張股票和選擇在未來不同天裡去賣掉那張股票。
你可以從這個交易回傳最大化的利潤。如果你無法達到任何利潤，就回傳 0。

題目連結：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

題目限制

注意：不能在第二天買入後第一天賣出，必須先買後賣。

1 <= prices.length <= 105
0 <= prices[i] <= 104

範例

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.
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.

思路&筆記

  • 判斷陣列中值的大小，把更小的值存起來
  • 兩數的相差 = 把當前的索引的值 - 上一個索引的值
  • 比較前一個值，將比較大的值存入

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxProfit(int[] prices) {
        
        int min = Integer.MAX_VALUE;  // 整數類型中的最大值 2³¹
        int op = 0;
        int pist = 0;
        
        for(int i = 0; i < prices.length; i++){
            
            // 找到陣列中最小的值
            if(prices[i] < min){
                min = prices[i]; // 前一個索引的值(最小的值)
            }
            
            // 兩數的相差 = 當前索引的值 - 前一個索引的值(最小的值)
            pist = prices[i] - min;
            
            // 比較前一個值，將比較大的值存入
            if(op < pist){  
                op = pist;
            }
        }
        return op;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        min = prices[0]; # 預設索引0
        op = 0;
        
        # 從索引1開始練遍歷
        for i in range(1,len(prices)):
            
            # 找出最小值
            if prices[i] < min :
                min = prices[i]
            
            # 把兩值的相差存入
            elif((prices[i] - min) > op): # 比較前一個值
                op = prices[i] - min # 將比較大的值存入
        
        return op;

成績

Language Runtime Memory
Java 2ms 59.4MB
Python 984 ms 25 MB