只能交易一次。
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 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。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
1暴力法解决
设置参数最大利润
然后两次循环
每次都算出利润来与最大利润比较
如果有比它大的则替代。
类似于求一个数组中的最大值或最小值的升级版本。
总共循环n*(n+1)/2
所以时间复杂度O(n2)
空间复杂度O(1)
package LeetCode_test;
public class MaxProflit {
public static void main(String[] args) {
}
public static int maxProfit(int[] prices) {
int maxprofit = 0;
for(int i = 0 ; i<prices.length-1 ;i++){
for(int j = i+1 ; j<prices.length;j++){
int profit = prices[j]-prices[i];
if(profit>maxprofit){
maxprofit = prices[j]-prices[i];
}
}
}
return maxprofit;
}
}
2一次循环法
public static int maxProfit(int[] prices) {
int maxprofit = 0;
int minprice = Integer.MAX_VALUE;
for(int i = 0 ; i<prices.length ;i++){
if(minprice>prices[i]){
//如果比最小值小则替换
minprice = prices[i];
}
else if(maxprofit<prices[i]-minprice){
//如果比最大利润大则替换
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
设立两个参数 最小值和最大利润
每次刷新最小值并且比较出最大利润
一次循环
所以时间复杂度为 O(n)
网友评论