1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录

[剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录

第 63 题:股票的最大利润

传送门:股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖交易该股票可能获得的利润是多少?

例如一只股票在某些时间节点的价格为 [9, 11, 8, 5, 7, 12, 16, 14]

如果我们能在价格为 5 的时候买入并在价格为 16 时卖出,则能收获最大的利润 11。

样例:

输入:[9, 11, 8, 5, 7, 12, 16, 14]

输出:11

思路:在过往的股价中找到最低价,“当前股价 – 最低价”为获利。遍历过程中,找到这个获利的最大值即可。由于只允许做一次股票买卖交易,枚举每一天作为卖出的日子,买入日子一定在卖出日子之前,为了获利最多,希望买入的日子的股票价格尽可能低。用 minnum 记录第 0 到 第 i 天的最低价格,则在第 i 天卖出的最大获利为 nums[i] - minnum,枚举 i 找到最大获利。

liwei2019101119_1.png

Python 代码:

  class Solution(object):
        def maxDiff(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            l = len(nums)
            if l == 0:
                return 0

            min_val = nums[0]
            max_profit = 0
            for i in range(1, l):
                min_val = min(min_val, nums[i])
                max_profit = max(max_profit, nums[i] - min_val)
            return max_profit

同 LeetCode 第 121 题。

传送门:121. 买卖股票的最佳时机

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

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

注意你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

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

Java 代码:

  public class Solution2 {

        // 留意这个解法的语义

        public int maxProfit(int[] prices) {
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) {
                // 在当前以及之前如果执行了买操作,能够得到的利润的最大值
                buy = Math.max(buy, -price);
                // 在当前以及之前如果执行了卖操作,能够得到的利润的最大值
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }

        public static void main(String[] args) {
            int[] prices = {7, 1, 5, 3, 6, 4};
            Solution2 solution2 = new Solution2();
            int maxProfit = solution2.maxProfit(prices);
            System.out.println(maxProfit);
        }
    }

区别于 LeetCode 第 122 题。

传送门: 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。

参考资料:从零开始学贪心算法 – CSDN博客 https://blog.csdn.net/qq_32400847/article/details/51336300

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录

链接:https://www.javajike.com/article/3303.html

« [剑指 Offer 第 2 版第 62 题] “孩子们的游戏(圆圈中最后剩下的数)”做题记录
[剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录»

相关推荐

QR code