Stock Span Problem
你会得到某只股票每天的收盘价：prices[i] 表示第 i 天的价格。第 i 天的跨度，是以第 i 天结束并包含当天的连续天数，在这些天里，价格都小于或等于 prices[i]。
按与 prices 相同的顺序，返回每天的跨度。每个跨度至少为 1，因为一天总会计入自身。
函数
- pricesinteger-array
- 按顺序列出每天的价格
- 返回值integer-array
- 每天的范围，顺序相同
约束条件
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- 价格相同的更早日期也计入跨度；只有严格高于当前价格的价格才会使跨度停止。
示例
- 输入
- prices = [31, 27, 14, 21, 30, 18, 40]
- 输出
- [1, 1, 1, 2, 4, 1, 7]
- 解释
- 第 3 天的 21 回溯到 14，并在 27 处停止：跨度为 2。第 4 天的 30 在 31 处停止：跨度为 4。第 6 天的 40 高于之前的所有价格，覆盖全部 7 天。
- 输入
- prices = [8, 8, 3, 8]
- 输出
- [1, 2, 1, 4]
- 解释
- 价格相等也计入范围，所以第 1 天价格为 8，覆盖第 0 天，得到 2。第 3 天价格为 8，覆盖当天和之前两个价格同为 8 的日期，范围为 4。
- 输入
- prices = [50, 40, 30, 20]
- 输出
- [1, 1, 1, 1]
- 解释
- 每天的价格都比前一天低，所以没有任何跨度会延伸到当天之前，每个跨度都是 1。
进阶
现在价格会一次到达一个，你必须在每个价格到达时报告对应的区间。哪种方法仍然有效？它会在多次调用之间保留什么？
提示
逐个打开提示，每个都会多透露一点。
每天都从当天往回数会重复工作：如果 8000 天的价格都相同，仅最后一天就要往回数 8000 天。从今天往回数时，哪些更早的日子可以直接跳过？
只要今天的价格至少和之前某一天一样高，之前那一天就不可能再成为后续时间段的阻挡点：今天更近，价格也至少一样高。只有那些价格高于其后所有日子的天仍然重要，而且这些天的价格从最早到最新依次降低。
按顺序遍历各天，并将仍然重要的更早日期作为索引保留在栈中。回答今天的问题前，弹出所有价格小于或等于今天价格的日期。栈为空表示跨度可以一直追溯到第 0 天；否则，跨度止于栈顶日期的后一天。然后将今天压入栈中。
题解
一天的跨度会在最近一个价格严格更高的更早日期处结束。向前查找需要为每天最多走 n 步。相反，只保留仍能阻止未来跨度的日期：用一个价格严格递减的索引栈，就能在一次遍历中找到所有边界。
每天都从后往前数
结果正确，但无法在最大的测试中运行完毕
思路
按照定义，对于第 i 天，每次往前退一天，直到当天的价格大于 prices[i]，并统计第 i 天。遇到第一个严格更高的价格，或到达数组开头时，遍历就结束。
每次遍历都不会复用之前的结果。价格持平或上涨时，每次遍历都会退回到第 0 天：n = 10^4 天意味着大约要执行 5 × 10^7 步。
算法
- 创建数组
span，使其长度与prices相同。 - 对于每一天
i，将计数器设为 0，并将指针j设为i。 - 当
j ≥ 0且prices[j] ≤ prices[i]时，将计数器加 1，并将j向前移动一天。 - 将计数器存入
span[i]。最后一天结束后，返回span。
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return span更高气温的单调栈
思路
把价格严格高于当天价格的最近一个更早日期称为阻挡日。跨度是 today - blocker；如果没有这样的日期，则为 today + 1。
在第一个示例中，第 3 天的价格是 21，第 4 天的价格是 30。之后每次遍历都会先到达第 4 天，而且任何能越过 30 的价格也能越过 21，因此第 3 天再也不可能成为阻挡日。一般来说，当遍历到今天时，所有价格不高于今天的更早候选日期都已经无效了：将它们弹出。此时栈顶剩下的日期就是今天的阻挡日。然后将今天入栈。
栈中价格从底到顶严格递减，因此第一个保留下来的日期就是最近的更高价格所在日期。在第一个示例中，第 4 天弹出第 3 天和第 1 天，然后停在第 0 天，跨度为 4 - 0 = 4。每一天只会入栈一次，弹出最多一次，因此这次遍历的运行时间为 O(n)。
算法
- 创建
span数组和一个用于存放日期索引的空栈。 - 对于每一天
today，当栈中索引对应的价格小于或等于prices[today]时，将这些索引从栈中弹出。 - 如果栈为空，跨度为
today + 1；否则，跨度为today减去栈顶的索引。 - 将
today入栈，然后进入下一天。返回span。
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
易错点和边界情况
- 使用
<而不是<=来弹出元素。在[8, 8, 3, 8]中，最后一天的跨度是 4；如果在前一个 8 处停止，跨度就会是 2。 - 栈为空时写成
today，而不是today + 1。第 0 天的跨度必须是 1，而不是 0。 - 每天只弹出一次元素。在第一个示例中，40 必须弹出第 5、4 和 0 天的元素。如果在第 5 天后停止，第 4 天看起来就像它的阻挡值，跨度会是 2，而不是 7。
- 在 Lua 和 R 中，数组从 1 开始。使用从 1 开始的索引时，栈为空时的跨度是
today，而不是today + 1。
常见问题4
股票跨度问题的时间复杂度是多少？
使用单调栈的时间复杂度为 O(n)，额外空间复杂度为 O(n)，因为每一天最多只会从栈中移出一次。如果价格持续上涨或保持不变，从每天开始向后遍历的时间复杂度为 O(n²)。
栈应该存储价格还是日期索引？
日期索引。跨度表示天数，只有阻挡项的索引能告诉你这一点。prices[index] 会读取价格，用于比较。
库存跨度问题可以在不使用单独的栈的情况下解决吗？
是的。从 j = today - 1 开始；当 j ≥ 0 且 prices[j] ≤ prices[today] 时，跳到 j - span[j]，因为这个跨度内的每一天价格都不高于 prices[j]。跨度是 today - j。这些跳转只会落在栈会保留的日期上，因此这一遍扫描的复杂度是 O(n)。
股票跨度问题是求前一个更大元素的问题吗？
是的，以天数为单位：对于每一天，找到价格严格更高且距离最近的更早一天，并报告它相隔多少天。反转扫描方向或比较条件，同一个栈就可以找到下一个更大值、下一个更小值或上一个更小值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def stockSpan(prices):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
prices = [31, 27, 14, 21, 30, 18, 40]
预期输出
[1, 1, 1, 2, 4, 1, 7]