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进行求解。他的大概思想就是将数组中相邻元素的差值(后减去前)重新组成一个数组,之后对这个求最大子序列和,详细介绍可以参考:
代码如下:
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; } };
推荐阅读
-
LeetCode_Array_123. Best Time to Buy and Sell Stock III买卖股票的最佳时机III(C++)
-
Leetcode No.121 Best Time to Buy and Sell Stock(c++实现)
-
309. Best Time to Buy and Sell Stock with Cooldown
-
Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
-
[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown
-
【DP + 卖股票】LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
-
LeetCode题解系列--309. Best Time to Buy and Sell Stock with Cooldown
-
动态规划-309. Best Time to Buy and Sell Stock with Cooldown
-
(M)Dynamic Programming:309. Best Time to Buy and Sell Stock with Cooldown
-
309. Best Time to Buy and Sell Stock with Cooldown