在数据结构的学习中，栈是一种非常重要的线性结构，它遵循后进先出（LIFO）的原则。而单调栈作为栈的一种变形，在解决一些特定问题时具有独特的优势。
一、单调栈的概念
单调栈是指栈内的元素保持单调性（单调递增或单调递减）的栈。例如，一个单调递增栈，从栈底到栈顶的元素值是逐渐增大的；单调递减栈则相反。
二、单调栈在“每日温度”问题中的应用
- 问题描述
- 给定一个表示每日温度的整数数组，对于每个温度，找出距离下一个更高温度的天数。
- 解题思路
- 我们使用单调递减栈来解决这个问题。栈中存放的是温度数组的下标。
- 当遍历到一个新的温度时，如果这个温度比栈顶元素对应的温度高，说明找到了栈顶元素的下一个更高温度。此时弹出栈顶元素，计算当前下标与栈顶元素下标的差值，这个差值就是所求的天数。
- 例如，温度数组为[73, 74, 75, 71, 69, 72, 76, 73]。开始时栈为空，遍历到73时，栈为空，直接入栈；遍历到74时，74大于栈顶的73，弹出73，计算74的下标1 - 73的下标0 = 1，然后将74入栈。继续这样操作直到遍历完整个数组。
三、单调栈在“直方图最大矩形”问题中的应用
- 问题描述
- 给定一个直方图，由一系列宽度为1的非负整数表示高度，求能构成的最大矩形面积。
- 解题思路
- 使用单调递增栈。栈中存放的是直方图的索引。
- 当遍历到一个新的高度时，如果这个高度小于栈顶元素对应的高度，说明以栈顶元素为高度的矩形可能已经到达了边界或者被当前高度限制。此时弹出栈顶元素，计算以弹出元素为高度的矩形面积。矩形的宽度是从当前下标到新的栈顶元素下标之间的距离。
- 比如直方图高度为[2, 1, 5, 6, 2, 3]。开始栈为空，遍历到2时入栈；遍历到1时，1小于栈顶的2，弹出2，计算面积为1 * 1 = 1（因为此时新的栈顶元素下标为0，当前下标为1）；然后将1入栈。
四、元素入栈时的弹出条件判断
- 在单调递增栈中的应用
- 当新元素要入栈时，如果新元素小于等于栈顶元素，则直接入栈。如果新元素大于栈顶元素，则不断弹出栈顶元素，直到栈为空或者栈顶元素大于新元素为止。这样就能保证栈的单调递增性。
- 在单调递减栈中的应用
- 当新元素要入栈时，如果新元素大于等于栈顶元素，则直接入栈。如果新元素小于栈顶元素，则不断弹出栈顶元素，直到栈为空或者栈顶元素小于新元素为止。从而维持栈的单调递减性。
总之，单调栈是一种非常有用的数据结构变形，在解决“每日温度”“直方图最大矩形”等问题时能够高效地得出结果。理解其元素入栈时的弹出条件判断是正确应用单调栈的关键所在。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
