每日温度 | 秋招知识库

视频讲解

为什么要用单调栈？请看单调栈【基础算法精讲 26】，欢迎点赞关注~

写法一：从右到左

栈中记录下一个更大元素的「候选项」的下标。

每次循环，我们可以在「候选项」中找到答案。

Python 解法1C++ 解法1

python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        st = []
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while st and t >= temperatures[st[-1]]:
                st.pop()
            if st:
                ans[i] = st[-1] - i
            st.append(i)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st;
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            while (!st.empty() && t >= temperatures[st.top()]) {
                st.pop();
            }
            if (!st.empty()) {
                ans[i] = st.top() - i;
            }
            st.push(i);
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $temperatures$ 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 $O (n)$ ，所以时间复杂度是 $O (n)$ 。
空间复杂度： $O (min (n, U))$ ，其中 $U = max (temperatures) - min (temperatures) + 1$ 。返回值不计入，仅考虑栈的最大空间消耗。

写法二：从左到右

栈中记录还没算出下一个更大元素的那些数的下标。

相当于栈是一个 todolist，在循环的过程中，现在还不知道答案是多少，在后面的循环中会算出答案。

Python 解法3C++ 解法3

python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        st = []  # todolist
        for i, t in enumerate(temperatures):
            while st and t > temperatures[st[-1]]:
                j = st.pop()
                ans[j] = i - j
            st.append(i)
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st; // todolist
        for (int i = 0; i < n; i++) {
            int t = temperatures[i];
            while (!st.empty() && t > temperatures[st.top()]) {
                int j = st.top();
                st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $temperatures$ 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 $O (n)$ ，所以时间复杂度是 $O (n)$ 。
空间复杂度： $O (n)$ 。注意这种写法栈中可以有重复元素。

更多相似题目，请看单调栈题单。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

写法一：从右到左 ​

复杂度分析 ​

写法二：从左到右 ​

复杂度分析 ​

分类题单 ​

视频讲解

写法一：从右到左

复杂度分析

写法二：从左到右

复杂度分析

分类题单