Leetcode第121題到123題連續(xù)出現(xiàn)了三道買賣股票相關(guān)的題目欣福，一年前的網(wǎng)易筆試和半年前的百度面試都遇到過121題责球，不過不用慌，看完本文拓劝，你一定能夠完美解決買賣股票的問題雏逾。那么我們由易到難，依次介紹這三道題目郑临。
121. Best Time to Buy and Sell Stock
121題題目是這樣的：
在所有的過程中栖博，我們只允許一次的買賣，基于這個問題牧抵，我們得到了下面的兩種解法笛匙。
解法1
根據(jù)題意侨把，我們只需要找出數(shù)組中最大的差值即可，即 max(prices[j] – prices[i]) 妹孙，i < j秋柄。
如何得到最大的差值，只需要一次遍歷即可蠢正，在遍歷的用一個變量記錄遍歷到當前時的最小值即可骇笔。時間復(fù)雜度為O(n).
相關(guān)的實現(xiàn)代碼如下：
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int min = prices[0];
int profit = 0;
// 第i天的價格可以看作是買入價也可以看作是賣出價
for (int i = 1; i < prices.length; i++) {
// 找到更低的買入價
if (min > prices[i]) {
// 更新買入價
min = prices[I];
}
// 當天的價格不低于買入價
else {
// 如果當天買出的價格比之前賣出的價格高
if (profit < prices[i] - min) {
// 更新賣出價
profit = prices[i] - min;
}
}
}
return profit;
}
}
解法2
第二題的解法是我在面試百度的時候想到的，應(yīng)用的是求數(shù)組中和最大的連續(xù)子數(shù)組序列的思路嚣崭，這種思路又被稱為Kadane's Algorithm笨触。我們有兩個問題：
如何轉(zhuǎn)化為求數(shù)組中的和最大的連續(xù)子序列？相鄰兩個數(shù)作差即可雹舀，這樣的話子序列的和就是我們在子序列開始賣出股票芦劣，在子序列最后買回股票所能得到的收益。
那么什么是Kadane's Algorithm呢说榆？
kadane算法利用了數(shù)學歸納法的思想虚吟。簡單來講就是，隨意給你一個現(xiàn)成的數(shù)組签财，比如說?2, 1, ?3, 4, ?1, 2, 1, ?5, 4串慰，讓你求其中的最大子列和，并不是容易的事情唱蒸。但如果我們能從第一個數(shù)開始邦鲫，隨著數(shù)組的擴充，始終對其最大子列和保持跟蹤神汹，就可以輕易的求出任意一個數(shù)組的最大子列和庆捺。換言之，長度n的數(shù)組我們不會求慎冤，長度為一的總能算出來吧疼燥？長度為一的算出來了，二也就能算出來蚁堤，二算出來了醉者，三就能算出來，以此類推披诗，用這種根據(jù)i求i+1的思想撬即，我們就能達到最終目的。
詳細的分析一下呈队，往一個長度為i的數(shù)組后面插入第i+1個數(shù)剥槐，這時，數(shù)組的最大子列只有兩種情況宪摧，要么包括第i+1個數(shù)粒竖，要么不包括第i+1個數(shù)颅崩。即：
maxsubarraum = max(以第i+1個數(shù)結(jié)尾的子列和， 不以第i+1個數(shù)結(jié)尾的子列和)蕊苗。*
先計算前者沿后，以第i+1個數(shù)結(jié)尾的子列和怎么算呢？很簡單朽砰，要么它是以第i個數(shù)結(jié)尾的子列作為前綴尖滚，要么它不以之作為前綴。假設(shè)第i+1個數(shù)為x瞧柔，那么：
以第i+1個數(shù)結(jié)尾的子列和 = max(x漆弄，以第i個數(shù)結(jié)尾的子列和+x) (1)。
再計算后者造锅，也就是不以第i+1個數(shù)結(jié)尾的子列和撼唾。這啥意思呢？其實就是插入第i+1個數(shù)之前的數(shù)組的最大子列和嘛备绽。我們的數(shù)學歸納思想也就體現(xiàn)在這里券坞，如果你還看不明白，我們將*式改寫：
數(shù)列長度i+1的最大子列和 = max(以第i+1個數(shù)結(jié)尾的子列和肺素， 數(shù)列長度i的最大子列和)。(2)
看到了吧宇驾，無論(1)式還是(2)式倍靡，后一種情況都可以由前一種情況推出，妥妥的數(shù)學歸納课舍。我們的算法只要從i=1開始塌西，一步一步按照上面的規(guī)則走下去，那么任意一個數(shù)列的最大子列和就能求出來了筝尾！
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int maxCur = 0;
int maxSoFar = 0;
for(int i=1;i<prices.length;i++){
maxCur = Math.max(0,Math.max(prices[i]-prices[i-1],maxCur + prices[i] - prices[i-1]));
maxSoFar = Math.max(maxCur,maxSoFar);
}
return maxSoFar;
}
}
122. Best Time to Buy and Sell Stock II
這道題的描述如下：
這道題允許無限次的買賣捡需，簡直太簡單了吧，只要后一天的價值比前一天的大筹淫，那就買賣唄站辉。不忍吐槽的一道題，代碼如下：
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int maxProf = 0;
for(int i = 1;i<prices.length;i++){
maxProf += (prices[i] > prices[i-1] ? prices[i] - prices[i-1]:0);
}
return maxProf;
}
}
123. Best Time to Buy and Sell Stock III
這一題還是比較難的损姜，題目描述如下：
我們只允許最多兩次的買賣饰剥，這可如何是好？我們同樣提供兩種思路：
解法1
這個問題可以轉(zhuǎn)換成Best Time to Buy and Sell Stock I問題摧阅。
兩次股票交易的核心是可以定義一個交易點汰蓉，在這個交易點之前可以做一次交易(賺的最大數(shù)目的錢為firstProf)，在這個交易點之后可以做一個交易(賺的最大數(shù)目的錢是secondProf)棒卷。那么要求的是max(firstProf+secondProf)顾孽。但是這個方法的時間復(fù)雜度是O(N^2)祝钢，空間復(fù)雜度是O(1)。leetcode中顯示超時若厚。
可以使用兩次掃描的方法避免上面的雙重循環(huán)拦英。
不同于Best Time to Buy and Sell Stock I中定義的初始狀態(tài)A[i]表示第i天賣出掙的最大數(shù)目的錢，這個更進一步直接定義A[i]表示前i天賺的最大數(shù)目的錢盹沈。minPrice表示從第0天到第i-1天中的最低價格龄章。
A[0]=0。（初始狀態(tài)）
A[1]=max(prices[1]-prices[0],A[0])
A[2]=max(prices[2]-minPrice,A[1])
.....
即A[i]=max(price[i]-minPrice,A[i-1]).
另外一次掃描從數(shù)組后向前掃描乞封，定義B[i]表示從第i天到最后一天n能賺的最大數(shù)目的錢做裙。maxPrice表示第i+1天到n天的最高價格。
B[n]=0肃晚。（初始狀態(tài)）
B[n-1]=max(maxPrice-prices[n-1],B[n])
B[n-2]=max(maxPrice-prices[n-2],B[n-1])
.....
即B[i]=max(maxPrice-prices[i],B[i+1])
那么以第i天為分割點能賺的最多數(shù)目的錢為A[i]+B[i]
問題的解為max{A[i]+B[i]}锚贱。0<=i<=n。
時間復(fù)雜度是O(N)关串，空間復(fù)雜度是O(N)拧廊。
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int[] asc = new int[prices.length];
int[] desc = new int[prices.length];
int n = prices.length;
int minprice = prices[0];
int maxProf = 0;
asc[0] = 0;
for(int i=1;i<n;i++){
asc[i] = Math.max(prices[i] - minprice,maxProf);
minprice = Math.min(prices[i],minprice);
maxProf = asc[i];
}
desc[prices.length-1] = 0;
maxProf = 0;
int maxprice = prices[prices.length-1];
for(int i=prices.length-2;i>=0;i--){
desc[i] = Math.max(maxprice-prices[i],maxProf);
maxprice = Math.max(maxprice,prices[i]);
maxProf = desc[i];
}
maxProf = 0;
for(int i=0;i<prices.length;i++){
maxProf = Math.max(maxProf,asc[i] + desc[i]);
}
return maxProf;
}
}
解法2
第二種解法的核心是假設(shè)手上最開始只有0元錢，那么如果買入股票的價格為price晋修，手上的錢需要減去這個price吧碾，如果賣出股票的價格為price，手上的錢需要加上這個price墓卦。
因此我們定義了4個狀態(tài)：
Buy1[i]表示前i天做第一筆交易買入股票后剩下的最多的錢倦春；
Sell1[i]表示前i天做第一筆交易賣出股票后剩下的最多的錢；
Buy2[i]表示前i天做第二筆交易買入股票后剩下的最多的錢落剪；
Sell2[i]表示前i天做第二筆交易賣出股票后剩下的最多的錢睁本；
那么假設(shè)我們在第i天時第二次賣出股票，我們賣出股票可以獲得Buy2[i-1]+prices[i]的錢忠怖，假設(shè)在第i天前已經(jīng)完成了兩筆交易呢堰，那么我們最多的錢是Sell2[i-1]，因此
Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}
同樣的道理凡泣，假設(shè)我們在第i天時第二次買入股票枉疼，我們手中的錢是Sell[i-1]-prices[i]，假設(shè)我們在第i天錢已經(jīng)賣出了兩次股票问麸，那么我們最多的錢是Buy2[i-1]往衷，因此
Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}
同樣的道理我們還可以得到：
Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}
Buy1[i]=max{Buy[i-1],-prices[I]}
可以發(fā)現(xiàn)上面四個狀態(tài)都是只與前一個狀態(tài)有關(guān)，所以可以不使用數(shù)組而是使用變量來存儲即可严卖。
這是leetcode中的討論網(wǎng)址：https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int sell2 = 0;
int sell1 = 0;
int buy1 = Integer.MIN_VALUE;
int buy2 = Integer.MIN_VALUE;
for(int i =0;i<prices.length;i++){
sell2 = Math.max(sell2,buy2+prices[i]);
buy2 = Math.max(buy2,sell1-prices[i]);
sell1 = Math.max(sell1,buy1+prices[i]);
buy1 = Math.max(buy1,-prices[i]);
}
return sell2;
}
}
參考文獻
1席舍、從一道easy leetcode問題，談?wù)勛畲笞恿泻偷腒adane算法：http://blog.csdn.net/The__Apollo/article/details/77367534
2哮笆、LeetCode123:Best Time to Buy and Sell Stock III：http://blog.csdn.net/u012501459/article/details/46514309
