关于后端: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]

提醒：

$1 <= temperatures.length <= 10^5$
$30 <= temperatures[i] <= 100$

为了不便，咱们令 temperatures 为 ts。

形象题意为 : 求解给定序列中每个地位（左边）最近一个比其大的地位，可应用「枯燥栈」来进行求解。

具体的，咱们能够从前往后解决所有的 $ts[i]$，应用某类容器装载咱们所有的「待更新」的地位（下标），假如以后解决到的是 $ts[i]$：

若其比容器内的任意地位（下标）对应温度要低，其必然不能更新任何地位（下标），将其也退出容器尾部（此时咱们发现，若有一个新的地位（下标）退出容器，其必然是以后所有待更新地位（下标）中的温度最低的，即容器内的温度枯燥递加）；
若其价格高于容器内的任一地位（下标）对应温度，其可能更新容器地位（下标）的答案，并且因为咱们容器满足枯燥递加个性，咱们必然可能从尾部开始取出待更新地位来进行更新答案，直到解决实现或遇到第一个无奈更新地位。

因为咱们须要往尾部增加和取出元素，因而容器可应用「栈」。

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

工夫复杂度：$O(n)$
空间复杂度：$O(n)$

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:739-每日温度-单调栈模板题

题目形容

枯燥栈

最初