LeetCode刷题实战121:买卖股票的最佳时机
共 1313字,需浏览 3分钟
·
2020-12-16 21:17
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
题意
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题
public int maxProfit(int[] prices) {
//解法一:蛮力法,找到每一天后续的最大值,比较确定最大利润
//时间复杂度:O(n^2),空间复杂度:O(1)
if(prices==null || prices.length==0)
return 0;
int maxprofit=0;
for(int i=0;ifor(int j=i+1;j //如果第i天买入,依次判断它之后的每一天卖出的情况
if(prices[j]-prices[i]>maxprofit)
maxprofit=prices[j]-prices[i];
}
}
return maxprofit;
}
在这里,我们只需要维护一个min变量,就可以省去一层循环,代码如下:
public int maxProfit(int[] prices) {
//解法二:动态规划法:用dp[i]表示第i天卖出的收益,则dp[i]=max(price[i]-min,maxProfit)
//时间复杂度:O(n),空间复杂度: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;iif(prices[i] //维护一个最小值
min=prices[i];
else if(prices[i]-min>maxprofit)
maxprofit=prices[i]-min;
}
return maxprofit;
}