🐵 什么是递增栈

1. 初始化一个空栈，作为递增栈。

2. 遍历待处理的元素，依次将它们压入递增栈中。

3. 在每次压栈之前，先将栈中比当前元素小的元素弹出栈，直到遇到一个比当前元素大的元素或者栈为空。

4. 将当前元素压入栈中。

5. 重复执行步骤 3 和步骤 4，直到遍历完成。

6. 遍历完成后，递增栈中的元素就是按照递增顺序排列的。

📢 使用场景

1. 找到数组中每个元素右边第一个比它大的元素。
在遍历数组时，使用递增栈来保存待处理的元素。在每次压栈之前，先将栈中比当前元素小的元素弹出栈，直到遇到一个比当前元素大的元素或者栈为空。然后将当前元素压入栈中。在遍历完成后，递增栈中的元素就是每个元素右边第一个比它大的元素。

2. 找到数组中每个元素左边第一个比它小的元素。
在遍历数组时，使用递减栈来保存待处理的元素。在每次压栈之前，先将栈中比当前元素大的元素弹出栈，直到遇到一个比当前元素小的元素或者栈为空。然后将当前元素压入栈中。在遍历完成后，递减栈中的元素就是每个元素左边第一个比它小的元素。

3. 找到数组中最大子矩阵的面积。
在这个问题中，我们需要找到一个矩阵中最大的子矩阵，并计算它的面积。可以使用递增栈来解决这个问题。首先，我们将矩阵的第一行作为初始值，然后依次处理每一行。对于每一行，我们将它的元素按照递增顺序排列，并计算以每个元素为高的最大矩形面积。具体地，我们使用递增栈来保存每一行中每个元素的位置，并计算以当前元素为高的最大矩形面积。在计算过程中，我们需要弹出栈中比当前元素小的元素，并计算以这些元素为高的最大矩形面积。最终，最大的矩形面积即为所求的最大子矩阵的面积。

🐝 LeetCode 算法题

1. LeetCode 84. Largest Rectangle in Histogram（直方图中最大的矩形）
在一个直方图中，每个柱子的宽度为 1，高度为给定的整数。找到直方图中面积最大的矩形。可以使用递增栈来解决这个问题。

2. LeetCode 739. Daily Temperatures（每日温度）
给定一个数组表示每日温度，要求对于每一天，计算出它需要等待多少天才能等到一个更高的温度。可以使用递增栈来解决这个问题。

3. LeetCode 901. Online Stock Span（股票价格跨度）
给定一个股票价格的序列，要求对于每一天，计算出它前面连续的天数中有多少天的价格小于等于它的价格。可以使用递增栈来解决这个问题。

4. LeetCode 496. Next Greater Element I（下一个更大元素 I）
给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，要求找到在 nums2 中比它大的下一个元素。可以使用递增栈来解决这个问题。

5. LeetCode 503. Next Greater Element II（下一个更大元素 II）
给定一个循环数组 nums，对于 nums 中的每个元素，要求找到在 nums 中比它大的下一个元素。可以使用递增栈来解决这个问题。

🔗 引用文章

• 无