買(mǎi)賣(mài)股票系列
【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) III
【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV
【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)包含冷凍期
開(kāi)源地址
為了便于大家學(xué)習(xí)钾军，所有實(shí)現(xiàn)均已開(kāi)源菩颖。歡迎 fork + star~
122. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
給你一個(gè)整數(shù)數(shù)組 prices 磺樱，其中 prices[i] 表示某支股票第 i 天的價(jià)格。
在每一天钉疫，你可以決定是否購(gòu)買(mǎi)和/或出售股票。你在任何時(shí)候 最多 只能持有 一股 股票。你也可以先購(gòu)買(mǎi)奄毡，然后在 同一天 出售。
返回 你能獲得的 最大 利潤(rùn) 贝或。
示例 1：
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋?zhuān)涸诘?2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入吼过，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4。
隨后咪奖，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入盗忱，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6 - 3 = 3。
最大總利潤(rùn)為 4 + 3 = 7 羊赵。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋?zhuān)涸诘?1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入趟佃，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4。
最大總利潤(rùn)為 4 昧捷。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋?zhuān)涸谶@種情況下, 交易無(wú)法獲得正利潤(rùn)闲昭，所以不參與交易可以獲得最大利潤(rùn)，最大利潤(rùn)為 0料身。
提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4
v1-上一題的思路延續(xù)
上一題
class Solution {
public int maxProfit(int[] prices) {
int maxResult = 0;
int minVal = prices[0];
for(int i = 0; i < prices.length; i++) {
minVal = Math.min(minVal, prices[i]);
maxResult = Math.max(prices[i] - minVal, maxResult);
}
return maxResult;
}
}
思路
因?yàn)榭梢詿o(wú)限次汤纸，獲取所有上升的區(qū)間利潤(rùn)即可。
改造一下
public int maxProfit(int[] prices) {
int maxResult = 0;
// int minVal = prices[0];
for(int i = 1; i < prices.length; i++) {
// minVal = Math.min(minVal, prices[i]);
maxResult += Math.max(prices[i] - prices[i-1], 0);
}
return maxResult;
}
v2-性能優(yōu)化
思路
下面的方式實(shí)現(xiàn)會(huì)更好一些芹血。
代碼
class Solution {
public int maxProfit(int[] prices) {
// 因?yàn)橹烂恳惶斓睦麧?rùn)贮泞，所以直接第二天高于今天楞慈，直接累加利潤(rùn)
int maxProfit = 0;
for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i-1]) {
maxProfit += prices[i] - prices[i-1];
}
}
return maxProfit;
}
}
效果
0ms 擊敗 100.00%
44.51MB 擊敗93.87%
V3-DP 的思路
思路
我們可以通過(guò)一個(gè)數(shù)組記錄每一次操作的最大利潤(rùn)。
b[n]
s[n]
每一次操作都可以決定是否操作啃擦。
遞推公式
// 是否賣(mài)出囊蓝？ 不賣(mài)； 賣(mài)出=上一次買(mǎi)入 + 當(dāng)前價(jià)格
// 是否買(mǎi)令蛉？ 不買(mǎi)聚霜； 買(mǎi)入=上一次賣(mài)出-當(dāng)前價(jià)格
代碼
public int maxProfit(int[] prices) {
int buy[] = new int[prices.length];
int sell[] = new int[prices.length];
buy[0] = -prices[0];
for(int i = 1; i < prices.length; i++) {
// 是否賣(mài)出？ 不賣(mài)珠叔； 賣(mài)出=上一次買(mǎi)入 + 當(dāng)前價(jià)格
sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i]);
// 是否買(mǎi)蝎宇？ 不買(mǎi)； 買(mǎi)入=上一次賣(mài)出-當(dāng)前價(jià)格
buy[i] = Math.max(buy[i-1], sell[i-1] - prices[i]);
}
return sell[prices.length-1];
}
小結(jié)
完整的思路祷安，只看對(duì)應(yīng)的波動(dòng)的山坡上升的地方姥芥。
不過(guò) dp 的思路是通用解法，我們理解之后汇鞭，更方便我們優(yōu)化凉唐。
參考資料
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
