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

动态规划 · curry · 于 24天前 发布 · 20 次阅读

题目描述

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

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

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