跳到主要内容

单调栈

1. 适用场景​

一般用于解决: 右侧（左侧）第一个大于（小于）的项这种题目。

2. 代码模版​

function firstMax(arr) {
  const stack = []
  const ans = new Array(arr.length).fill(-1)

  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      const index = stack.pop()
      ans[index] = i - index
    }
    stack.push(i)
  }

  return ans
}
提示

操作栈最好还是使用 stack[stack.length - 1] 和 push，虽然使用 stack[0] 和 shift 在写代码的时候会方便一点， 但是 shift 理论上是会移动数组中所有的项，在极端情况下可能会超时

3. 题目​