121. 买卖股票的最佳时机（ Best Time to Buy and Sell Stock）

题目地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解题思路一：暴力求解法

　　根据题目我们可以知道，我们知道最大利润“i”-“j”的差值就可以得到结果，所以时间复杂度为O（n*n）,空间复杂度为O（1）。以下为源码：

  int maxProfit(vector<int>& prices) {

           int size=prices.size();

        if(size<=)

        {

            return ;

        }

        int max=;

        for(int i=;i<size-;i++)

        {

            for(int j=i+;j<size;j++)

            {

                if(prices[j]-prices[i]>max)

                    max=prices[j]-prices[i];

            }

        }

        return max;

    }

结果是不出意外的超时了。

解题思路二：

　　暴力求解的思路超时是由于执行了许多没必要的计算过程，我们现在来开辟一下思路。

如上图所示：

最大利润其实在图中找到峰谷和峰顶（峰顶出现在峰谷之后），两者高度就是最大利润。因为主要的限制条件在于峰顶出现在峰谷之后，如果我们确定当前的峰谷，那么之后出现的最高峰就是卖出股票的地方。

　　当之后出现新的峰谷（记为P）比当前峰谷（current）还低的话，此时的最大利润只有两种可能，一种为当前峰谷和新峰谷出现之后最高顶的差值，一种为新峰谷之后和以后出现峰顶的差值。因此我们需要记录峰谷的值和最大利润，每次出现更低的峰谷，我们就需要更新，因为这时候老的峰谷对后面结果没有影响了。

 int maxProfit(vector<int>& prices) {

           int size=prices.size();

        if(size<=)

        {

            return ;

        }

        int min=prices[];

        int maxprices=-;

        for(int i=;i<size;i++)

        {

            if(prices[i]<min)

            {

                min=prices[i];//新的峰谷

            }

            else

            {

                if(prices[i]-min>maxprices)

                    maxprices=prices[i]-min;

            }

        }

        return  maxprices;

    }

巴特西

121. 买卖股票的最佳时机（ Best Time to Buy and Sell Stock）

最新文章

热门文章