这次来分析一下LeetCode中几道炒股题目
No.121 买卖股票的最佳时机
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
1
2
3
4
| 输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
|
示例 2：
1
2
3
| 输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
|
踩坑思路
一开始想对每个元素，往前找最大值，可是这个题目的数据范围非常大，超时了。
基于这个想法，马上想到，超时是因为重复计算，比如找到一个最大值之后，我就不用每次都找最大值了，想到第二种思路，就是找到最大值之后，在子区间找最小值，然后从最大值的下一个位置开始继续找。这时候又面临另外的情况：
- 数组是单调递减的时候，反复找依然很浪费时间
- 摆动数组：还是浪费时间。
于是这个版本的代码也超时了。
最后看答案找到第三种解法——滚动法。因为题目限制了只买卖一次，那我就假设，一开始是第一天买入的，从前往后遍历：
- 遍历到位置i的时候就假设是那天卖出去，看能捞多少钱，如果比已知最大利润更大那就更新最大利润。
- 如果遍历找到一个更小的价格，那就按照那个价格买入。这时候注意，因为是从前往后遍历，所以不会存在找到最小值之后倒车卖出（最大值出现在最小值之前）的可能性，只是滚动更新买入价格而已。
这次终于不超时了。
1
2
3
4
5
6
7
8
9
10
| class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
buyin = prices[0]
for price in prices:
if price - buyin > res:
res = price - buyin
if price < buyin:
buyin = price
return res
|
运行结果：
1
2
3
4
| Accepted
211/211 cases passed (96 ms)
Your runtime beats 98.87 % of python3 submissions
Your memory usage beats 85.42 % of python3 submissions (23.3 MB)
|
No.122 买卖股票的最佳时机 II
题目描述
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
1
2
3
4
5
| 输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
|
示例 2：
1
2
3
4
| 输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
|
示例 3：
1
2
3
| 输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
|
解题思路
这个反而感觉比121还要简单一些，比121多了多次交易这个条件。我的实现思路是不断找单调递增子序列。子序列的起点为买入时间，子序列的终点是卖出时间。这里有个边界条件是，在序列遍历结束之后，如果买入日期不是-1，那就意味从买入日期开始到最后构成一个单调递增子序列，需要在最后一天卖出，赚最后一手钱。
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
prev = prices[0]
start = -1
for idx, price in enumerate(prices):
if price > prev and start == -1:
start = idx - 1
elif price < prev and start != -1:
end = idx - 1
res += (prices[end] - prices[start])
start = -1
prev = price
if start != -1:
# 说明到最后一天还没卖出，那就在最后一天卖出
res += (prices[-1] - prices[start])
return res
|
901 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
1
2
3
4
5
6
7
8
9
10
11
| 输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
|
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
这道题又一次死在了单调栈。
思路分析
一开始看错题目，以为要找数组中比这个价格小的，gg
看清楚题目之后，用暴力解法，超时。超时原因在于对每个入栈元素都往前判断，题目对时间限制很严格。
最后看答案才解决问题。有一个很关键的突破口被我忽视了：对进来的每天股票的价格，如果这个价格比以前的价格低，那么以前的这些价格都不会参与到后续的计算了（因为不可能再构成单调减序列）。
因此，维护一个单调栈，栈顶元素就是到前一天的价格，不过进栈有讲究：
- 如果比前一天的小，那就进栈，天数
+1 - 如果比前一天的大，那就将栈里元素出栈，直到栈里元素都比当前元素大，把当前元素进栈。
还有个讲究就是，进栈的不仅仅是元素，还有当天的答案。每次出栈的时候，把天数给加起来。为当前元素获得的答案。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
| class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
res = 1
while self.stack and self.stack[-1][0] <= price:
res += self.stack.pop()[1]
self.stack.append((price, res))
return res
|
运行结果
1
2
3
4
| Accepted
99/99 cases passed (340 ms)
Your runtime beats 40.35 % of python3 submissions
Your memory usage beats 90.02 % of python3 submissions (19.6 MB)
|