# [LeetCode 739] 经典递增栈

虽然是个很经典的递增栈,但我忘了咋写……知道思路但写不出来的感觉实在是🤢。

基本思路就是倒序遍历,去掉栈里比它小的元素,保持这个栈整体是递增的。这样,只需要和栈顶进行比较。

这里存的是下标,因为题目求的是距离。

function dailyTemperatures(T: number[]): number[] {
  const length = T.length,
    res = new Array(length).fill(0),
    stack: number[] = [];
  for (let i = length - 1; i >= 0; --i) {
    while (stack.length && T[stack[stack.length - 1]] <= T[i]) {
      stack.pop();
    }
    const stackLength = stack.length;
    if (stackLength) {
      res[i] = stack[stackLength - 1] - i;
    }
    stack.push(i);
  }
  return res;
}
最后更新于: 6/25/2020, 2:10:06 PM