前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天一道leetcode121-买卖股票的最佳时机

每天一道leetcode121-买卖股票的最佳时机

作者头像
乔戈里
发布2019-01-11 11:59:47
9760
发布2019-01-11 11:59:47
举报
文章被收录于专栏:Java那些事

121_(买卖股票的最佳时机)Best Time to Buy and Sell Stock

1 问题描述、输入输出与样例

1.1 问题描述

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

1.2 输入与输出

输入:

  • vector & prices:长度可变的价格数组prices

输出:

  • int:所能获取的最大利润

1.3 样例

1.3.1 样例1

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

1.3.2 样例2

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

2 思路描述与代码

2.1 思路描述(动态规划法)

dp[i] 表示为第 i + 1 天可获得的最大利润; 此时最大利润可能是下述两种情况:

  1. 当前卖出的的情况是prices[i]-最低价
  2. 不是当天卖出的情况是dp[i-1] 于是dp[i] = max(prices[i]-最低价, dp[i-1]); dp中只与前一个元素有关,可以写成简化空间复杂度的写法:max_profit = max(prices[i]-最低价, max_profit)。

比如输入: [7,1,5,3,6,4]; i = 0, min_price = 7, dp[0] = 0; i = 1, min_price = 1, dp[1] = min(0, 0) = 0; i = 2, min_price = 1, dp[2] = min(5 - 1, 0) = 4; i = 3, min_price = 1, dp[3] = min(3 - 1, 4) = 4; i = 4, min_price = 1, dp[4] = min(6 - 1, 4) = 5; i = 5, min_price = 1, dp[5] = min(4 - 1, 5) = 5;

2.2 代码

代码语言:javascript
复制
//函数中涉及到的c++知识
//vector<int> 是个长度可变的 int 数组,c++里面称为容器
int maxProfit(vector<int>& prices) {
    int len = prices.size();
    //边界情况
    if(len == 0) return 0;

    //当前最大的利益 = max(前一天可能的最大利益, 今天的价钱-最低价)
    int max_profit = -2147483648;
    int min_price = 2147483647;
    for( int i = 0; i < prices.size(); i++ ){
        min_price = min(min_price, prices[i]);
        max_profit = max(max_profit, prices[i] - min_price);
    }
    return max_profit;
}

3 思考与拓展

3.1 思考

本题通过分析在第 x 天可能卖出的最大收益的情况可以很快推出动态规划的递推表达式,然后再做空间的简化即可。

3.1.1 其他方法
3.1.1.1 差分+最大连续子列和
  1. 先求差分数组
  2. 求差分数组中的最大连续子列和
3.1.2 复杂度分析

方法

空间复杂度

时间复杂度

动态规划法

O(1)

O(n)

差分+最大连续子列和

O(n)

O(n)

3.1.3 难点分析
  1. 求递归表达式
  2. 简化空间复杂度

3.2 拓展

  1. 买卖股票的最佳时机 II。
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-01-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 121_(买卖股票的最佳时机)Best Time to Buy and Sell Stock
  • 1 问题描述、输入输出与样例
    • 1.1 问题描述
      • 1.2 输入与输出
        • 1.3 样例
          • 1.3.1 样例1
          • 1.3.2 样例2
      • 2 思路描述与代码
        • 2.1 思路描述(动态规划法)
          • 2.2 代码
          • 3 思考与拓展
            • 3.1 思考
              • 3.1.1 其他方法
              • 3.1.1.1 差分+最大连续子列和
              • 3.1.2 复杂度分析
              • 3.1.3 难点分析
            • 3.2 拓展
            相关产品与服务
            容器服务
            腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档