leetcode 0121.best-time-to-buy-and-sell-stock

Spread the love

我的思路:

首先假设第一天肯定买进,然后从第二天开始看

情况一:如果第二天的价格低于第一天,那就以第二天的买价为准

以此类推

情况二:如果盈利天时,就开始计算之后每一天的差价,并记录最高价

每次发现有情况二发生,比较当前差价和上次计算差价,取其最大值

结论:8800ms 问题在情况2判断是 时间复杂度在o(n)级别

对比参考答案

发现盈利天时,将当天受益和当前最佳受益(初始值0,即平仓线)直接对比

如果当天收益更高,直接更新最佳受益计数

结论:60ms

总结:

条件一,找买入时机,条件二,找卖出时机

This entry was posted in leetcode. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *