只赢不亏的买股票的方法
前言
大家好，我是来自于华为的程序员小熊。今天给大家带来一道与贪心算法相关的题目，这道题同时也是字节、苹果和亚马逊等互联网大厂的面试题，即力扣上买卖股票的最佳时机 II。
本文主要介绍贪心的策略来解答此题，供大家参考，希望对大家有所帮助。
买卖股票的最佳时机 II
题目描述
示例
解题思路
贪心算法是通过做出一系列选择来求出问题的最优解，在每个决策点，它做出当时看来最佳的选择。通过局部最优的选择，寄希望实现全局最优解。
举例
以 prices = [1,4,2,3,7] 为例子，求获得的最大利润，如下图示。
例子
遍历数组 prices，第一天一定买入；
第一次决策
尔后判断判断第二天的价格是否大于第一天，大于则卖出（局部最优）；
价格递增时决策
卖出后，如果后面一天的价格小于当天的价格，则当天不买，防止亏本；
价格递减时决策
以此类推，其采用贪心策略买卖股票的完整决策过程如下动图示：
决策的整个过程
Show me the Code
「C」
int maxProfit(int* prices, int pricesSize){
int ans = 0;
for (int i = 1; i < pricesSize; ++i) {
/* 后一天的价格比前一天高，则卖出（当前最佳策略） */
ans += fmax(0, prices[i] - prices[i - 1]);
}
return ans;
}
「C++」
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i = 1; i < prices.size(); ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
「Java」
int maxProfit(int[] prices) {
int ans = 0;
for (int i = 1; i < prices.length; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}
「Python3」
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1, len(prices)):
ans += max(0, prices[i] - prices[i - 1])
return ans
「Golang」
func maxProfit(prices []int) int {
ans := 0
for i := 1; i < len(prices); i++ {
profit := prices[i] - prices[i-1]
if profit > 0 {
ans += profit
}
}
return ans
}
复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度，需要遍历一遍数组。
空间复杂度：O(1)，未开辟额外的空间。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-07-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录