Leetcode之PHP版题目解析(122. Best Time to Buy and Sell Stock II)

2019-3-10 星期日   开始吧


刚才在群里和skys大佬聊天,大佬说断更的体验不好。是的,断更的体验确实不好,相对于我来说,可能突然断了两天三天自己的惰性都出来了,周日的话我一般喜欢看点别的书,或者约上几个老友一起打球,所以想了一下,可能我以后会在周一到周五的时候多刷几道,然后先更新在公众号,周末的时候我相当于再温习一遍了,两全其美。那么开始吧。


27160e7f6e0e68a4db97d50db46afa0a.png


今天的标题还是最佳买入和卖出的时间.上一版Leetcode基础刷题之(121. Best Time to Buy and Sell Stock)


题目描述

给定一个数组,其中第i个的数值是第i天给定的股票的价格.计算出它最大的利润空间(卖出的钱减去买入的钱就是你的利润空间),和昨天不同的是,昨天只能买入一次,然后卖出,今天的题目可以多次交易(可以多次买入卖出一只股票).但是你不能同时进行多笔交易,也就是说,你再购买前,得先确保已经卖掉了之前买入的.


题目思路

我的思路就是循环整个数组,从第一个数开始比较,只要后一个数大于前一个数,说明此时就是有利润空间的,按照这样的流程走,只要有利润空间我就卖出,最后把所有的利润空间值和在一起,就是所能获取的最大利润.


实现代码

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


运行结果

1169e3304ededc41be8f4fa0f56dfd2b.png

时间复杂度分析

这里有一个for循环,循环的次数取决于数组的个数,时间复杂度就是O(n),存储的是个恒定的空间,所以空间复杂度是O(1)。




吴亲库里 has written 35 articles

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

积分:1817 等级:P6 职业:php 城市:杭州

0 条回复

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