单调栈

单调栈是一种特殊的栈结构，它保证栈内元素按照某种单调性（递增或递减）排列。就像排队时要求身高从低到高或从高到低一样，单调栈在插入新元素时会“清理”掉破坏单调性的元素，从而保持栈内有序。这种结构常用于解决与“下一个更大/更小元素”相关的问题。

给定一个数组，要找到每个元素右边第一个比它大的元素。单调栈的做法是：从左到右遍历数组，维护一个单调递减栈（栈底到栈顶递减）。当遇到一个新元素时，如果它比栈顶元素大，说明栈顶元素的“下一个更大元素”就是当前元素，于是弹出栈顶并记录答案。重复这个过程，直到栈为空或当前元素不大于栈顶，然后将当前元素入栈。这样，每个元素在出栈时就知道它的下一个更大元素了。

每个元素最多入栈一次、出栈一次。遍历数组时，每个元素被压入栈一次；当它被弹出时，是因为遇到了更大的元素，且弹出后不再入栈。因此，总操作次数与数组长度 n 成正比，时间复杂度为 O(n)。空间复杂度也是 O(n)，因为栈最多存储 n 个元素。

简单记忆：要找“更大”就用递减栈（栈顶最小），要找“更小”就用递增栈（栈顶最大）。

每日温度：求每个温度后面第一个更高温度的天数差，直接用单调递减栈，记录下标差即可。

接雨水：用单调递减栈，当遇到比栈顶高的柱子时，弹出栈顶作为凹槽底部，计算当前柱子与新的栈顶形成的雨水面积。

柱状图最大矩形：用单调递增栈，遍历每个柱子高度，当遇到比栈顶矮的柱子时，弹出栈顶并计算以该高度为高的矩形面积（宽度由当前下标与新的栈顶下标决定）。