买卖股票的最佳时机|刷题打卡

我心飞翔 分类:javascript

前言

本文正在参与掘金团队号上线活动,点击查看大厂春招职位。

题目

给定一个数组 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、设置一个变量maxProfit来存放最大利润,并且给个默认值为0.

2、遍历价格数组

3、然后遍历到每个价格时,取接下来几天中价格最高的数与之相减,如果没有,那么默认这一天买入的价格,不过哪一天卖出,利润都是0。

4、如果我们相减后的数比之前的maxProfit大,那么就将maxProfit设置成新的最大利润。

时间复杂度: O(n^2)。

但是我们发现用了这个方法后,在力扣中执行时,超时了!那怎么办呢?所以我们又想到了另一种方法

方法二:

我们假设每一天都有可能卖出,那么最大利润就是在这一天的价格最低的一天买入,那么我们可以怎么做呢?

1、设置一个价格最小值变量minPrice,默认值设置为price[0],设置利润最大值变量maxProfit,默认值为0。

2、遍历数组,如果当前价格比minPrice小,就将当前价格设置为最新的minPrice; 如果当前价格比Price大,那就减去minPrice,如果减下来的数大于原先的最大值变量,就将maxProfit设置成新减得到的数。

时间复杂度: O(n)。

AC代码

方法一:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;

    for(let i=0; i < prices.length; i++) {
        const maxPrice = Math.max(...prices.slice(i+1));

        if(maxPrice > prices[i] && (maxPrice - prices[i] > maxProfit)) {
            maxProfit = maxPrice - prices[i];
        }
    }

    return maxProfit;
};
 

方法二:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;
    let minPrice = prices[0]

    for(let i=0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }

        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }

    return maxProfit;
};
 

总结

这个题目如果让我们单纯想到一个解决方案是非常容易的,但是如何减少时间复杂度,处理大量数据不超时,是我们需要注意的,这告诉我们,去实现一个算法时,不仅要可以实现功能,同时要注意它的时间空间复杂度,尤其是循环套循环的方式,不在万不得已最好不要使用,时间复杂度非常高,一旦数据量很大,就很有可能超时。

回复

我来回复
  • 暂无回复内容