Leetcode No.121 Best Time to Buy and Sell Stock(c++实现)

1. 题目

1.1 英文题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

1.2 中文题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

1.3输入输出

输入 输出
prices = [7,1,5,3,6,4] 5
prices = [7,6,4,3,1] 0

1.4 约束条件

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

2. 实验平台

IDE:VS2019
IDE版本:16.10.1
语言:c++11

3. 分析

这一题最简单粗暴的方法就是穷举枚举,代码为:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.size() - 1; i++)
        {
            for (int j = i + 1; j < prices.size(); j++)
            {
                int temp = prices[j] - prices[i];
                if ( temp > maxprofit)
                {
                    maxprofit = temp;
                }
            }
        }
        return maxprofit;
    }
};

这样做只适用于数据较少的情形,而对于大数据很容易造成超时现象,那么能不能进行优化一下,我想到了双指针法,快指针负责遍历整个数组,当快指针的值小于等于慢指针的值时,将慢指针指向快指针指向的位置。新代码如下:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans;
        for(int i = 0; i < rowIndex + 1; i++)
        {
            vector<int> temp(i + 1);
            temp[0] = temp[i] = 1;
            for(int j = 1; j < i; j++)
            {
                temp[j] = ans[j - 1] + ans[j]; 
            }
            ans = temp;
        }
        return ans;
    }
};

但是我们提交后发现算法时间和空间复杂度都没变,于是我在想还有没有优化空间,我发现每行计算时都需要重新定义temp,并为其开辟内存空间,有待优化,故可以将其提前定义,并在每行计算时重定义temp大小,代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int slow = 0;
        int max = 0;
        int temp = 0;
        for (int quick = 1; quick < prices.size(); quick++)
        {
            temp = prices[quick] - prices[slow];
            if (temp <= 0) slow = quick;
            else if (temp > max) max = temp;
        }
        return max;
    }
};

这次性能不错。在写这段程序的过程中,我最开始是将temp在for循环内进行定义并赋值,但是我发现如果把它放在外面定义,可以优化算法的时间和空间复杂度,于是我想到,变量的定义也是需要消耗时间和空间的,因此最好是提前定义好,也就是尽量减少定义次数。
另外,在题目的solution中我还发现大佬用Kadane's Algorithm进行求解。他的大概思想就是将数组中相邻元素的差值(后减去前)重新组成一个数组,之后对这个求最大子序列和,详细介绍可以参考:https://blog.csdn.net/shendezhuti/article/details/105114569
代码如下:

class Solution {
public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
};
上一篇:CF 867E. Buy Low Sell High(反悔贪心+堆)


下一篇:LeetCode:Database 104.按日期分组销售产品