Leetcode基础刷题之(121. Best Time to Buy and Sell Stock)

2019-3-6   


申明一下:可能你看到的题目不是按照顺序排下来的,原因有二:1是我刚做这个没多久,所以我是先从easy开始做的,Medium和Hard我是直接先跳过去的,一步步来.然后就是前面的easy在写这个之前已经刷了大半部分了,可能后面写的时候会再拿出来求最优解(其实是测试自己之前有没有忘光).之前用php写的放在GitHub一个仓库上了,等数量再多一点,解题水平高一点在拿出来吧.没出意外的话,周一到周五每天一篇.



1a682d61e9718d50a69185109fcb4581.png


目描述


ii果要求),润(最大的卖出值-减去最小的买入值)



1[7,1,5,3,6,4],16么最大5


2[7,6,4,3,1]。只会一直亏损



0果当前循环中值存入我们预先定义的变量中。然后遍历整个数组,最后得出最大的利润空间.


     /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $min=$prices[0];
        $max=0;
        for($i=0;$i<count($prices);$i++) {
            if($min>$prices[$i]) {
                $min=$prices[$i];
            }
            
            $max=max($prices[$i]-$min,$max);
        }
        return $max;
    }

时间复杂度分析

一个for循环,取决于数组$prices的个数n,所以时间复杂度是O(n),空间复杂是常量O(1).

吴亲库里 has written 86 articles

情绪只是对自己无能的愤怒

积分:4182 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?