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

Leetcode · curry · 于 2个月前 发布 · 66 次阅读

题目描述

给定一个数组,其中第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;
}

时间复杂度分析

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

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 0 条回复 动态规划 php 算法
没有找到数据。
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂