# 单调栈算法

单调栈是一种特殊的栈，栈中的所有元素单调递增或者单调递减。注意，单调递增栈是指栈中元素从栈底到栈顶是递增的。栈顶值为栈中所有元素的最大值或最小值。

单调栈在算法中的应用在于它能够在一次扫描，即 O(n) 的复杂度之内找到数组中每一个元素的前(后)上界(单增栈)或者前(后)下界(单减栈)。

它主要用于解决一些与数组中元素相对大小关系有关的问题，例如找到数组中某个元素的下一个更大元素、上一个更小元素等。

# 单调栈算法处理步骤

对于单调栈的处理如下。首先遍历一次数组，在遍历数组时，对于每个元素，将其与栈顶元素比较，会有以下两种情况：

如果栈为空，或者当前元素比栈顶元素满足单调性（对于单调递增栈，当前元素大于栈顶元素；对于单调递减栈，当前元素小于栈顶元素），将元素压入栈中。
如果当前元素破坏了单调性，不断地将栈顶元素弹出，同时处理该元素的信息（根据具体问题进行相应的操作），直到栈为空或满足单调性后，将当前元素压入栈中。

之后，选择恰当的时机更新结果。需要注意的是，在遍历结束后，栈中可能还会有一些元素没有被处理完，这些元素的处理方式也要根据具体问题进行相应的操作。

# 单调栈算法模板

以这道题为例：

上一个更小元素（Next Smaller Element）：对于数组中的每个元素，找到其左侧第一个比它小的元素。

例如，给定数组 [2, 1, 2, 4, 3]，对于元素 3 ，其上一个更小元素是 2。

我们可以先给出单调栈算法的模板：

// 单调栈算法模板（单调递增栈为例）
function monotonicStack(arr) {
  // 维护单调递增栈，栈顶最小
  const stack = [];

  // 遍历找到每个元素的 上一个更小元素
  for (let i = 0; i < n; i++) {
    // 若栈顶元素比当前元素大，弹出去不要，维持栈单调递增
    while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
      const top = stack.pop();

      // 处理逻辑可选位置 1
      if (stack.length === 0) break;
      const current = stack[stack.length - 1];
      //  处理弹出元素与栈顶元素的关系，更新结果，如接雨水
      result = update(current, top, i);
      // 处理结束
    }

    // 处理逻辑可选位置 2
    if (stack.length === 0) continue;
    const current = stack[stack.length - 1];
    // 处理栈顶元素的，更新结果，如找到上一个更小元素
    result = update(current, i);
    // 处理结束

    // 将当前元素压入栈中
    stack.push(i);
  }

  return result;
}

# 模板变体

那么问题来了，我们能不能用单调栈算法解决上一个更大元素问题呢？答案当然是可以的，我们只需要将单调栈的比较条件改为：

// 若栈顶元素比当前元素小，弹出去不要，维持栈单调递减
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
  const top = stack.pop();
  ...
}

那么如果我们想求下一个更小元素，或者下一个更大元素呢？也简单，只需要将遍历数组的顺序改为从右到左即可。

// 从右到左遍历
for (let i = n - 1; i >= 0; i--) {...}

# 题型参考

496. 下一个更大元素 I
503. 下一个更大元素 II
739. 每日温度
42. 接雨水
84. 柱状图中最大的矩形

← 图遍历算法滑动窗口算法 →