JZX轻语：简
LeetCode 901 - 股票价格跨度
发表于2024年05月22日
本质问题就是对于每个元素，求解左边第一个比其大的元素下标，此时两个下标的跨度即所需结果。此类问题(1. 对于每个子问题(数组的每个元素)，求解元素单侧比它大/小的第一个元素; 2. 如果维护子问题的结果)，均可以使用单调栈来求解。
class StockSpanner:
def __init__(self):
self._stack = [] # typing.List[typing.Tuple[int, int]]
self._next_pos = 0
def next(self, price: int) -> int:
while self._stack and self._stack[-1][0] <= price:
self._stack.pop()
ans = self._next_pos - (self._stack[-1][1] if self._stack else -1)
self._stack.append((price, self._next_pos))
self._next_pos += 1
return ans