Loading...
墨滴

Shinkai005

2021/12/15  阅读:33  主题:红绯

# 【leetcode】100.相同的树(2)

【leetcode】122.买卖股票的最佳时机

题目描述

image-20211214111751219
image-20211214111751219

题目思路

[7,1,5,3,6,4]

输出7

前提: 上帝视角,知道未来价格;

贪心算法: 局部最优:见好就收,见差不动,不做任何长远打算.

个人题解

/**
 * @param {number[]} prices
 * @return {number}
 */

var maxProfit = function (prices{
    /**
     新建一个变量,用来统计利润
     遍历价格数组,如果比昨天高,就在昨天买,今天卖,否则不交易.
     遍历结束返回变量
     */

    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
};

总结优化

这块有个问题哦,

题目例二: [1,2,3,4,5] 题目是结果为4. 第一天买第5天卖

但是我们用贪心算法其实是,第一天买第二天卖 第二天买第三天卖...结果也是4

因此,贪心算法并没有想象中那么好那么便捷,但是在特定场合下确实优秀.

再次写一下贪心算法的原理

一种期待局部最优以达到全局最优的算法.

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(1)

Shinkai005

2021/12/15  阅读:33  主题:红绯

作者介绍

Shinkai005