Leetcode PHP题解--D109 122. Best Time to Buy and Sell Stock II

D109 122. Best Time to Buy and Sell Stock II

题目链接

122. Best Time to Buy and Sell Stock II

题目分析

给定一个数组，代表商品价格。从给定的数组中，计算通过买卖能获得的最大收益。只有卖出才能再买入。

思路

一开始以为是获取最小值右边的最大值去卖出。

后来发现规律，是在价格拐点进行买入卖出操作。

即，先单调递减后单调递增时买入，先单调递增后单调递减时卖出。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $profit = 0;
        $buyIndex = -1;
        $days = count($prices);
        $increasing = ($prices[0]<$prices[1]);
        if($increasing){
            $buyIndex = 0;
        }
        for($i=1; $i<$days; $i++){
            //if is increasing perviously
            if($increasing){
                //but starts to decrease
                //than its time to sell
                if($prices[$i]>$prices[$i+1]){
                    if($buyIndex != -1 ){
                        $profit += $prices[$i]-$prices[$buyIndex];
                    }
                    $buyIndex = $i+1;
                    $increasing = false;
                }
            }
            else{ //decreasing
                //starts
                if($prices[$i]<$prices[$i+1]){
                    $buyIndex = $i;
                    $increasing = true;
                }
            }
        }
        return $profit;
    }
}

我个人认为这个函数并没有使用很复杂的算法，但是只打败了28.36%。内存占用只打败了15.79%。有很大的改进空间。

若觉得本文章对你有用，欢迎用爱发电资助。