算法练习第八天——买卖股票的最佳时机

简介: 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

算法练习第八天——买卖股票的最佳时机


算法练习第八天——买卖股票的最佳时机


买卖股票的最佳时机题目


给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。


你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。


返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。


示例一:


输入: prices = [7,6,5,4,3,2,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


示例二:


输入: prices = [7,2,4,3,1,9,8] 输出: 7 解释: 在第二天买入,第六天卖出,为最大利润7。


解题思路


方法一:一次遍历


我们只要用一个变量记录一个历史最低价格 minvalue,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minvalue。


因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。


以下代码以golang为例:

func maxProfit(prices []int) int {
  minValue := math.MaxInt64
  maxValue := 0
  for i := 0; i < len(prices); i++ {
    if prices[i] < minValue {
      minValue = prices[i]
    } else if prices[i]-minValue > maxValue {
      maxValue = prices[i] - minValue
    }
  }
  return maxValue
}

该解法复杂度分析


  • 时间复杂度:O(n),需要遍历一次。


  • 空间复杂度:O(1),只使用了常数个变量。
相关文章
|
6月前
|
存储 算法 索引
模拟算法题练习(二)(DNA序列修正、无尽的石头)
模拟算法题练习(二)(DNA序列修正、无尽的石头)
|
6月前
|
并行计算 算法 测试技术
模拟算法题练习(一)(扫雷,灌溉,回文日期)
模拟算法题练习(一)(扫雷,灌溉,回文日期)
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
6月前
|
数据采集 监控 算法
应用动态规划算法解决可转债软件中的最优买卖时机问题
使用动态规划算法解决可转债市场的最佳买卖时机问题。定义状态dp[i][0](持有可转债的最大利润)和dp[i][1](不持有可转债的最大利润),通过状态转移方程更新状态,以max函数求解。提供的Python代码示例展示了如何计算最大利润。将此算法集成到软件中,结合网络爬虫获取实时价格,自动计算并提供买卖建议,助力投资者做出更明智的决策。
128 0
|
6月前
|
算法 数据可视化 数据挖掘
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
|
6月前
|
机器学习/深度学习 自然语言处理 算法
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(下)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
|
6月前
|
机器学习/深度学习 算法 大数据
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(上)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
|
6月前
|
算法 Java 索引
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
[Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读
47 0
|
6月前
|
存储 算法 JavaScript
JS算法-买卖股票的时机
JS算法-买卖股票的时机
|
6月前
|
存储 算法 搜索推荐
Leetcode算法题练习(一)
Leetcode算法题练习(一)
81 0