专栏首页小浩算法《剑指offer》第19天:股票交易(校对)

《剑指offer》第19天:股票交易(校对)

01、题目分析

在leetcode上,股票相关的题目有8道之多:

而且这一类型的题,面试时出现的频率非常的高。稍微改一改条件,就让我们防不胜防。那我们如何攻克这一类题型呢?我们从较为简单的一道开始看起:

第122题:买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4

解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。

因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目分析:首先我们看一下题目中给出的两个条件:

1、不能参与多笔交易。换句话讲,我们只能在手上没有股票的时候买入,也就是必须在再次购买前出售掉之前的股票。像我们平时买股票时的追涨杀跌是不可以的。

2、尽可能地多进行交易。这个非常好理解。像是黄金,一年基本上都有2-3次涨跌。我们只要把握住机会,在每一次涨跌的时候,低价卖入高价卖出,就可以使利益达到最大化。这个条件也是相当重要的,如果我们把这里变成,最多完成两笔交易,就变成另一道题。

现在题目搞清楚了,我们来思考一下。

02、题解分析

假设给定的数组为:[7, 1, 5, 3, 6, 4] 我们将其绘制成折线图,大概是下面这样:

如我们上面分析,我们要在满足1和2的条件下获取最大利益,其实就是尽可能多的低价买入高价卖出。而每一次上升波段,其实就是一次低价买入高价卖出。而我们没有限制交易次数,也就是我们需要求出所有的上升波段的和。上图里就是A+B,也就是(5-1)+(6-3) = 7,就是我们能获取到的最大利益。

其实也就是尽可能多的低价买入,高价卖出啦。

03、代码分析

根据以上分析,我们很容易得到题解,先给一个 go 实现的动态规划的版本:

//GO
func maxProfit(prices []int) int {
    if len(prices) < 2 {
        return 0
    }
    dp := make([][2]int, len(prices))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i := 1; i < len(prices); i++ {
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])
    }
    return dp[len(prices)-1][0]
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}

当然,大家要是觉得上面的内容不过瘾,我们也可以给出一个 java 版本的代码。这次我们用贪心进行实现:

//JAVA
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                profit += diff;
            }
        }
        return profit;
    }
}

04、题目扩展

图解的方式其实在各种算法题中,屡见不鲜。而我们通过图解的方式,也可以抽丝剥茧一样,一层一层剥掉算法题目的外壳,寻找到最直观的解题思路,直捣黄....咳咳,直奔核心。那我们又如何用图解的观察方式,来对本系列的其他题目寻找到一种通用解法,来规避题目中的陷阱呢?

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第26天:最大子序和

    首先我们分析题目,一个连续子数组一定要以一个数作为结尾,那么我们可以将状态定义成如下:

    程序员小浩
  • 小姐姐提灯给你讲讲动态规划(万字长文)

    我们把要解决的一个大问题转换成若干个规模较小的同类型问题,当我们求解出这些小问题的答案,大问题便不攻自破。这就是动态规划。

    程序员小浩
  • 漫画:BAT必考题目 (如何压缩状态完成不同路径题目)

    不同路径:一个机器人位于一个 m x n 网格的左上角,起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,在下...

    程序员小浩
  • 【leetcode】Best Time to Buy and Sell Stock

    Say you have an array for which the ith element is the price of a given stock on...

    阳光岛主
  • LeetCode 188. Best Time to Buy and Sell Stock IV (动态规划)

    题意:给你一个数组代表每天的股价。你有k次买入和卖出的机会,问你最多能赚多少钱。买入之前必须卖出已有股份。同一天是可以先买,再卖,或者先卖再买的。

    ShenduCC
  • [Leetcode][python]Best Time to Buy and Sell Stock I/II/III/买卖股票的最佳时机

    给定每天的股票价格,如果只允许进行一轮交易,也就是买进一次和卖出一次,求所能获得的最大的利润。

    后端技术漫谈
  • LeetCode 121. 买卖股票的最佳时机

    如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

    freesan44
  • DP专题 5 | 颜色的长度 - UVA1625(线性DP)

    题目链接 https://cn.vjudge.net/problem/UVA-1625

    ACM算法日常
  • 中小型数据库 RMAN CATALOG 备份恢复方案(三)

          在前两篇文章中描述了中小型数据库使用RMAN catalog设计备份与恢复方案,并给出了所有相关的脚本来从某种车程度上模拟Oracle Data G...

    Leshami
  • LeetCode 64. Minimum Path Sum

    ShenduCC

扫码关注云+社区

领取腾讯云代金券