发表于 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

• LC 题目链接