LeetCode-121. Best Time to Buy and Sell Stock
難度: easy
You are given an array
priceswhereprices[i]is the price of a given stock on theithday.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]為 ith 天的股價
你要透過選一天作為買入股票的日期，另一天作為賣出股票的日期，來最大化你的獲利。
回傳你能夠透過交易得到的最大獲利，如果沒有辦法則回傳0
(鳥翻譯請見諒，如有錯誤請協助指出，感謝
Example 1:
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:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
解題流程
- 先看懂題目想描述甚麼情境
- 開始想像程式運作該經過哪些流程
- 將經過的流程所需的判斷跟細節列出
- 實作列出的流程
先看懂題目想描述甚麼情境
應該是描述股票買賣，買進跟賣出要不同天，要算出最大的獲利，所以要取得所有天數內，賣出 – 買進最大的值。
開始想像程式運作該經過哪些流程
想像中應該會有一天買進，一天賣出，遍歷所有天數取得買進跟賣出差異最大的獲利，賣出的日期一定是在買入之後，當今天買入的值大於賣出的值，之後有機會取得最大的獲利值得買入日期一定是目前賣出的日期(因為值比較小)，然後賣出的日期應該是要變成從買入的日期下一天來算。
題目有提到要回傳最大的獲利值，所以在每次的判斷後，看看是否比之前取得的獲利多記錄起來，最後回傳就好。
將經過的流程所需的判斷跟細節列出
一天買進一天賣出，買進跟賣出一定是不同天，這邊有一個要注意的地方是所有日期有可能是1(1 <= prices.length)，但因為買進跟賣出必須是不同日期，所以這個情況應該要直接結束判斷回傳沒有獲利。
一開始先想到的流程是
既然買進一定是賣出之後，那從日期的最後一天來往回數買進最小值是多少，但後來才發現，其實從一開始算或是最後算都可以，因為主要應該是要判斷，取得最大獲利的區間 = 買入日為最低價格 & 賣出日為最高價格，可以將買進日或賣出日其中一方先固定，另外一邊繼續走，邊走邊算是否目前獲利大於之前算出的最大獲利。
如果是固定買入日的話—————————————————————-
將所有天數陣列(prices)的開頭設為買入日，隔天設為賣出日，算一下目前獲利(賣出 – 買入)。
如果獲利大於最高獲利初始值(0)，當作第一筆最高獲利。
判斷如果獲利價格 < 0 ————————————————————
表示目前買入價格 > 賣出價格，得知下一個買入最小值為賣出價格，買入日改為賣出日，因為賣出日必須在買入之後的不同天，所以將賣出日設為買入日的下一天。
判斷如果獲利價格 > 0 ————————————————————
表示目前的買入價格< 賣出價格，基於這個買入價格我們可以繼續試試看其他的賣出日，所以只要移動賣出日到下一天即可。
——————————————————————————————-
PS: 示範程式碼是固定賣出日來做判斷，判斷的邏輯會是一樣的，只是先將賣出日期固定，往回找目前賣出日最小的買入日期。
實作列出的流程
typescript
function maxProfit(prices: number[]): number {
/**
is buying then selling
so selling date must different and after buying date
we need to find the largest selling date and smallest buying date
we can put the selling date as the last index of array
buying date is the date before selling date at first
then check if selling date is over buying date
it means we can keep looking if there's a smaller buying date
otherwise we should put selling date as buying date
and buying date is the date before selling date
*/
/**
since we can know the largest selling date when we keep moving the selling date
the condition to break the loop is when the selling date is before the first date in array
*/
let maxProfit = 0;
if(prices.length === 1) return maxProfit;
let sellingDate = prices.length - 1;
let buyingDate = sellingDate - 1;
while(buyingDate >= 0) {
const profit = prices[sellingDate] - prices[buyingDate];
if(profit > maxProfit) {
maxProfit = profit;
}
if(profit < 0) {
sellingDate = buyingDate;
}
buyingDate--
}
return maxProfit;
};感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教