leetcode算法121.買賣股票的最好時機

哈喽！大家好，我是【學無止境小奇】，一位熱愛分享各種技術的部落客！

⭐【學無止境小奇】的創作宗旨：每一條指令都親自執行過，每一行代碼都實際運作過，每一種方法都真實實踐過，每一篇文章都良心制作過。✊✊✊

⭐【學無止境小奇】的部落格中所有涉及指令、代碼的地方，除了提供圖檔供大家參考，另外會在圖檔下方提供一份純文字格式的指令或者代碼友善大家粘貼複制直接執行指令或者運作代碼。

⭐如果你對技術有着濃厚的興趣，歡迎關注【學無止境小奇】，歡迎大家和我一起交流。

❤️❤️❤️感謝各位朋友接下來的閱讀❤️❤️❤️

文章目錄

• ​​一、leetcode算法​​

• ​​ 1、買賣股票的最佳時機​​

• ​​1.1、題目​​
• ​​1.2、思路​​
• ​​1.3、答案​​

一、leetcode算法

1、買賣股票的最佳時機

1.1、題目

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你隻能選擇 某一天 買入這隻股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能擷取的最大利潤。

傳回你可以從這筆交易中擷取的最大利潤。如果你不能擷取任何利潤，傳回 0 。

示例 1：

輸入：[7,1,5,3,6,4]

輸出：5

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。

注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

示例 2：

輸入：prices = [7,6,4,3,1]

輸出：0

解釋：在這種情況下, 沒有交易完成, 是以最大利潤為 0。

1.2、思路

思路一：此題用暴力解法複雜度太高，我們可以通過一輪循環找出答案，首先我們檢視規律，我們首先要找到股票最低點買入，然後記錄每一天如果賣股票的話賺的最高點。

1.3、答案

class Solution {
    public int maxProfit(int[] prices) {
        //定義股票最低的價格
        int minprice = Integer.MAX_VALUE;
        //定義股票最高的價格
        int maxProfit = 0;
        //循環記錄股票最低的一天的價格，和股票相差最大的價格
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < minprice){
                minprice = prices[i];
            }else if(prices[i] - minprice > maxProfit){
                maxProfit = prices[i] - minprice;
            }
        }
        return maxProfit;
    }
}      

複雜度分析

時間複雜度：O(n)，隻需要周遊一次。