?LeetCode刷題實(shí)戰(zhàn)121：買賣股票的最佳時(shí)機(jī)

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 。
?????注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

public?int?maxProfit(int[] prices) {
????????//解法一：蠻力法，找到每一天后續(xù)的最大值，比較確定最大利潤(rùn)
????????//時(shí)間復(fù)雜度：O(n^2),空間復(fù)雜度：O(1)
????????if(prices==null?|| prices.length==0)
????????????return?0;
????????int?maxprofit=0;
????????for(int?i=0;i????????????for(int?j=i+1;j//如果第i天買入，依次判斷它之后的每一天賣出的情況
????????????????if(prices[j]-prices[i]>maxprofit)
????????????????????maxprofit=prices[j]-prices[i];
????????????}
????????}
????????return?maxprofit;
????}

public?int?maxProfit(int[] prices) {
????????//解法二：動(dòng)態(tài)規(guī)劃法：用dp[i]表示第i天賣出的收益，則dp[i]=max(price[i]-min,maxProfit)
????????//時(shí)間復(fù)雜度：O(n),空間復(fù)雜度：O(1)
????????if(prices==null?|| prices.length==0)
????????????return?0;
????????int?len=prices.length;
????????int?maxprofit=0,min=Integer.MAX_VALUE;
????????for(int?i=0;i????????????if(prices[i]//維護(hù)一個(gè)最小值
????????????????min=prices[i];
????????????else?if(prices[i]-min>maxprofit)
????????????????maxprofit=prices[i]-min;
????????}
????????return?maxprofit;
????}