前言
歡迎閱讀小王同學的長篇連載文章之《每天學一道leetcode》。
如果您從前做過這道題目,可以從小王同學的文章裡增強對該題目的記憶和印象,思考一下小王同學給出的思路和解法有沒有優化的空間。
如果您從前沒有做過這道題,不妨跟小王同學一起學習一下解題思路,以後面試的時候也許會有妙用。
如果您對互聯網技術、算法知識、程序員個人發展感興趣,歡迎關注小王同學,小王同學將會在該領域持續更新。
同時,如果您有任何建議或者想法,歡迎留言給小王。
題目描述
這是一道難度為簡單的題目,股票交易問題在Leetcode上一共有4個問題,這是該系列問題中的第一題。
同時,這道題也是面試中經常考察的高頻題目。
讓我們開始看一看這道題吧。
題目分析
輸入一個數組代表一段時間內每天股票的價格,讓我們設計一個算法,求一次交易(一次買賣)最大的收益。
首先想到的是,我們要求出最大收益,我們應該找到滿足在時序的前提下,找到時序上的最小值和最大值。
問題的難點在於如何在滿足時序的前提下,保證找到正確的最小值和最大值。
怎麼辦呢?讓我們來看一下解題思路。
解題思路
對於輸入數組,我們肯定是要選擇從前向後遍歷,爭取一次遍歷完成。
在這個過程中,我們需要先設置一些變量。
我們首先設置變量profit作為我們的返回值,也就是最大利潤。
接下來設置min變量,用於存放遍歷到的最小价格。
接下來開始遍歷。
我們首先對每一個數組元素(價格)與當前min做差,求出當前位置的利潤profit。
接下來,隨著遍歷的過程,不斷記錄遍歷到的最小值,存入min變量。
這樣,我們始終能得到到當前位置最小的價格。
因此,我們每一輪求到的profit都是在當前遍歷位置最大的profit。
最後,我們在每次遍歷的時候,更新profit為max(profit,nums[i]-min),就保持住了最大的利潤profit。
示例代碼
最後
關於每天一道Leetcode系列文章還在持續更新,歡迎關注小王同學一起學習~
不積跬步,無以至千里。
一天一道LeetCode,用三個月的閒暇時間,就能積累一百道題。
堅持半年,就能學會200道題。
與君共勉。
閱讀更多 互聯網老農民小王 的文章