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

2019-3-6 星期三  那么开始把

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

题目描述

给定一个数组，其中第i个元素是第i天股票的价格，如果要求你只能完成一笔交易（买入卖出）,用一个算法求出你最大的利润(最大的卖出值-减去最小的买入值)。

题目案列

实例1给定的数组是[7,1,5,3,6,4],那么他的最大利润应该是第二天买入的1，然后在第五天也就是价值为6的时候卖点，那么最大利润就是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).