宫水三叶的刷题日记

V1

2022/10/01阅读:22主题:前端之巅同款

739. 每日温度 : 单调栈模板题

题目描述

这是 LeetCode 上的 739. 每日温度 ,难度为 中等

Tag : 「单调栈」

给定一个整数数组 temperatures,表示每天的温度,返回一个数组 answer,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]

输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]

输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]

输出: [1,1,0]

提示:

单调栈

为了方便,我们令 temperaturests

抽象题意为 : 求解给定序列中每个位置(右边)最近一个比其大的位置,可使用「单调栈」来进行求解。

具体的,我们可以从前往后处理所有的 ,使用某类容器装载我们所有的「待更新」的位置(下标),假设当前处理到的是

  • 若其比容器内的任意位置(下标)对应温度要低,其必然不能更新任何位置(下标),将其也加入容器尾部(此时我们发现,若有一个新的位置(下标)加入容器,其必然是当前所有待更新位置(下标)中的温度最低的,即容器内的温度单调递减);

  • 若其价格高于容器内的任一位置(下标)对应温度,其能够更新容器位置(下标)的答案,并且由于我们容器满足单调递减特性,我们必然能够从尾部开始取出待更新位置来进行更新答案,直到处理完成或遇到第一个无法更新位置。

由于我们需要往尾部添加和取出元素,因此容器可使用「栈」。

Java 代码:

class Solution {
    public int[] dailyTemperatures(int[] ts) {
        int n = ts.length;
        int[] ans = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && ts[d.peekLast()] < ts[i]) {
                int idx = d.pollLast();
                ans[idx] = i - idx;
            }
            d.addLast(i);
        }
        return ans;
    }
}

TypeScript 代码:

function dailyTemperatures(ts: number[]): number[] {
    const n = ts.length
    const ans = new Array<number>(n).fill(0)
    const stk = new Array<number>(n).fill(-1)
    let he = 0, ta = 0
    for (let i = 0; i < n; i++) {
        while (he < ta && ts[stk[ta - 1]] < ts[i]) {
            const idx = stk[--ta]
            ans[idx] = i - idx
        }
        stk[ta++] = i
    }
    return ans
};

Python3 代码:

class Solution:
    def dailyTemperatures(self, ts: List[int]) -> List[int]:
        n, he, ta = len(ts), 0, 0
        ans, stk = [0] * n, [-1] * n
        for i in range(n):
            while he < ta and ts[stk[ta - 1]] < ts[i]:
                ta -= 1
                idx = stk[ta]
                ans[idx] = i - idx
            stk[ta] = i
            ta += 1
        return ans
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.739 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1