leetcode(30)单调栈

6077. 巫师的总力量和

注意：因为要求连续，所以不能用回溯的方法做

496. 下一个更大元素 I

907. 子数组的最小值之和
908. 子数组最小乘积的最大值
909. 子数组范围和

901. 股票价格跨度

用单调栈维护一个单调递减的价格序列，并且对于每个价格，存储一个 weight 表示它离上一个价格之间（即最近的一个大于它的价格之间）的天数。
如果是栈底的价格，则存储它本身对应的天数。例如 [11, 3, 9, 5, 6, 4, 7] 对应的单调栈为 (11, weight=1), (9, weight=2), (7, weight=4)。

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight

173. 二叉搜索树迭代器

先把根节点及其左子树存入，然后依次出栈；每次调用next判断有右子树，则同样入栈

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        cur = self.stack.pop()
        node = cur.right
        while node:
            self.stack.append(node)
            node = node.left
        return cur.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

参考资料：
单调栈 + 前缀和的前缀和
前缀和 + 单调栈，拆成三个小问题逐步破解