03—买卖股票的最佳时机【LeetCode121】

吃猫的鱼Code

发布于 2023-07-24 18:28:16

1330

发布于 2023-07-24 18:28:16

文章被收录于专栏：吃猫的鱼个人博客编程笔记吃猫的鱼个人博客编程笔记

题目

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

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

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

来源：力扣（LeetCode 121）

示例一：

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

示例二：

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

解题

解法一

思路

首先定义两个数组L R，L[i]记录的prices[i]天以及之前股票的最小价格（最多到maxLength-2索引处，因为最后一天是只能买，没有机会卖，所以不必统计），R[i]记录的prices[i]天后面股票的最大价格（最多到1索引处，因为第一天只能只能买，不能卖，所以不必统计），首先对两个数组L R 进行填充，填充满后，然后对进行遍历，找出L[i] - R[i] 的最大值（范围为1-maxLength-2），要是所有值均小于等于0，表示没有交易完成，最大利润为0。

注意当前算法对于数组长度为1或者2的输入，需要进行额外判断！

解决

public int maxProfit(int[] prices) {
        int maxLength = prices.length;
        int[] L = new int[maxLength];
        int[] R = new int[maxLength];
        int[] result = new int[maxLength];
        //记录最好收益，最终返回结果
        int bestIncome = 0;
        //做个简单的判断，要是数组长度小于等于2的情况，单独处理
        if(maxLength<=2){
            if(maxLength==1){
                return bestIncome;
            }
            //要是数组长度为2 ， 三目运算，要是后面的值减前面的值大于0，直接返回值，否则返回0
            return prices[1]-prices[0]>0?prices[1]-prices[0]:0;
        }
        //初始化L数组，当i为0的时候，L[0]默认为prices[0]
        L[0] = prices[0];
        //开始填充L数组，从索引1处开始遍历
        for(int i=1;i0;i--){ //不用轮到索引0处，因为索引0的时候还没有股票不能卖出
            if(prices[i]>R[i+1]){       //找最大价格
                R[i] = prices[i];
            }else{
                R[i] = R[i+1];
            }
        }
        for(int i=1;i

`结果`

> 2023/07/14 10:55:54    
解答成功:
    执行耗时:4 ms,击败了21.52% 的Java用户
    内存消耗:56.2 MB,击败了87.97% 的Java用户

`解法二`

`思路`

记录【今天之前买入的最小值】
计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
比较【每天的最大获利】，取最大值即可

`解决`

public int maxProfit(int[] prices) {
        if(prices.length<=1){
            return 0;
        }
        int min = prices[0];        //最小价格
        int max = 0;                //最大获利
        for(int i=1;i

`结果`

> 2023/07/14 11:13:23    
解答成功:
    执行耗时:2 ms,击败了43.37% 的Java用户
    内存消耗:57.7 MB,击败了55.55% 的Java用户

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

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

int

本文分享自作者个人站点/博客?前往查看

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

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度