初级算法-数组-买卖股票的最佳时机
2021-07-27 本文已影响0人
coenen
给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
摘一个示例做个说明.
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,
在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4
在第 4 天(股票价格 = 3)的时候买入
在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3。
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
条件分析:
- 给一个数组,数据是每天的股票价格 -> 提前知道股票所有价格
- 多次买卖同一只股票 -> 手里只能有一只股票
- 不能同时参与多笔交易 -> 买了必须卖出,卖出后才能买.不能有留存
- 提示说明不是大量数据 -> 说明数据量用的
解决思路1:
- 根据条件1,说明我们已经提前知道了股票的涨跌,即涨势图已知
- 根据条件2、3,说明只能全买或者全卖
根据涨势我们可以确认是否盈利,根据前一天的价格,如果当天盈利,就相当于卖出,如果不盈利,就买入.如图示:
1.png如果比前一天是涨的,我就认为我持有这部分收益,如果是持续跌的,我就不买入,坚守股市的低买高卖即可方便理解.当作自己就是巴菲特,能最低买最高卖.
所以只需要与前一天比较即可.如果是涨,就收益.这样就达到最大收益.
代码实现-Swift版本:
思路1代码:
func maxProfit(_ prices: [Int]) -> Int {
if prices.count < 2 {
return 0;
}
var max = 0
for i in 0 ..< prices.count - 1 {
if prices[i] < prices[i + 1] {
max = max + prices[i + 1] - prices[i]
}
}
return max
}
思路1 提交结果.png
测试用例:
// 只有一个元素
let nums0: [Int] = [3]
// 只有两个相同元素
let nums1: [Int] = [1,1]
// 只有两个不相同元素
let nums2: [Int] = [1,3]
// 先涨
let nums3: [Int] = [1,5,7,8,4,2,7,10,9,3]
// 先跌
let nums4: [Int] = [8,5,2,3,4,6,10,8,19,9]
// 全跌
let nums5: [Int] = [31,25,20,18,14,9,6,3,2,1]
// 全涨
let nums6: [Int] = [1,2,3,4,5,6,7,8,9,15]
考察要点:
- 贪心
- 数组
- 动态规划