在线股票跨度：编码问题解答
Source: Dev.to
Problem Overview
Online Stock Span 是一种流式问题，考察你在增量处理数据的同时，如何以智能、压缩的方式保存过去信息。你会一次收到每日的股票价格，对于每一个新价格，都需要计算它的跨度。
股票价格的跨度定义为：在当日及之前连续的天数（包括今天），这些天的价格都小于或等于今天的价格。
例如，如果今天的价格高于昨天和前天的价格，那么跨度就包括这几天。如果今天的价格低于昨天的价格，则跨度仅为 1。
关键约束是这是一道 在线（online）问题。你无法看到未来的价格，必须在每次查询到达时立即给出答案。这也是它与经典的基于数组的股票问题不同之处。
为什么朴素方法会失效
一种直接的方法是从今天向后查看，统计有多少连续的前一天价格小于或等于当前价格。
这对单一天有效，但如果价格持续上升，你每次都会向更远的过去扫描。最坏情况下，这会导致二次时间复杂度。
面试官使用这个问题来判断你是否能够避免重复工作，并识别出可以“跳过”不必要比较的模式。
解决方案背后的关键思路
核心洞察在于，并非所有之前的日子都同等重要。
如果某一天的价格较低，而随后出现了一天更高的价格，那么这一天单独出现时将永远不再重要。它被更新、更高的价格“覆盖”了。
这一观察直接引出了使用 单调栈 的思路。
想了解更多编码题目解法？请查看 Binary Tree Zigzag Level Order Traversal 和 Binary Search Tree Iterator。
堆栈式方法工作原理
-
维护一个栈，其中每个条目代表前一天，存储：
- 价格
- 与该价格关联的跨度
栈从底部到顶部保持价格严格递减的顺序。
-
当出现新价格时，先为今天设定跨度为 1。
-
查看栈顶：
- 如果栈顶价格 ≤ 今天的价格，则今天的跨度包括该条目所代表的所有天数。将其跨度加到今天的跨度上，并弹出该条目。
- 重复此过程，直到栈为空或栈顶价格 > 今天的价格。
-
将今天的价格及其计算得到的跨度压入栈中。
-
你刚刚计算的跨度就是今天的答案。
为什么这样在概念上有效
每个栈条目代表一段连续的天数，这些天数的价格都小于栈中它们下面的价格。
通过弹出并合并区间，你可以把许多较小的天数合并成一个条目。这避免了对同一天的重复扫描。
每一天的价格只会被压入栈一次，最多弹出一次，即使在价格持续上升的长序列中也能保证效率。
为什么在实践中高效
虽然单个交易日可能会导致栈中出现多次弹出，但这些弹出在不同的日子之间不会重复。
在整个价格序列中，压入和弹出的总次数是 线性 的。这意味着每个操作的平均时间是常数，即使单个步骤看起来更复杂。
这种“摊销”效率是面试官常常希望你能够解释的概念。
常见的候选人错误
- 仅存储价格并手动重新计算跨度，这会失去压缩的优势。
- 误解比较条件：题目明确说明“小于或等于”，仅使用“小于”会导致错误结果。
- 忘记这是一个在线问题，试图预处理整个数组，从而偏离了题目的要点。