☆打卡算法☆LeetCode 121. 买卖股票的最佳时机 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“在一个数组中，从前往后找两个数，找出后面减前面数字的最大值。”

题目链接：

来源：力扣（LeetCode）

链接： 121. 买卖股票的最佳时机

2、题目描述

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

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

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

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

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

二、解题

1、思路分析

这道题很容易想到的就是使用两层循环，然后遍历找出数组中两个数字之间的最大差值，而且第二个数字必须大于第一个数字，代码参考：

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

这么写的算法，时间复杂度为O(n²)，那能不能降到O(n)呢？

假设我们已经买了一个最低价格minprice，然后在第i天卖出，能得到的利润就是prices[i]-minprice。

那么就只需要遍历一遍数组，记录买入的最低价格minprice，然后计算每天卖出能赚多少钱，最大值就是答案。

2、代码实现

代码参考：

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

只需要遍历一遍数组。

空间复杂度： O(1)

只是用了常数级空间的变量。

三、总结

先得到一个最低值，然后判断每天卖出得到的利润。

得到卖出时间的最大差值，再从中取最大值。