欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-19 12:58:56
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 choosin ......

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进行求解。他的大概思想就是将数组中相邻元素的差值(后减去前)重新组成一个数组,之后对这个求最大子序列和,详细介绍可以参考:
代码如下:

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;
    }
};