力扣第739题 每日温度 c++ 单调栈 Java

力扣第739题 每日温度 c++ 单调栈 Java

题目

739. 每日温度

中等

相关标签

栈   数组   单调栈

给定一个整数数组 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 <= 105
• 30 <= temperatures[i] <= 100

思路和解题方法

• 在这个函数中，首先创建了一个栈 st 用于存储数组 t 的索引，同时初始化了一个与数组 t 大小相同的结果数组 ans，初始值全部为 0。
• 接下来，从数组 t 的第二个元素开始遍历，对于每个元素，如果它的温度小于等于栈顶元素对应的温度，就将其索引压入栈中；否则，需要找到对应栈顶元素的下一个更暖和的温度。在这种情况下，通过一个循环不断弹出栈顶元素，直到找到比当前元素温度高的位置，更新结果数组 ans 中对应位置的值为当前索引与栈顶索引的差值，然后将当前索引压入栈中。
• 最后，返回结果数组 ans。

• 当使用单调栈时，我们希望能够维护一个递减（对于寻找下一个更高温度的问题）或者递增（对于寻找下一个更低温度的问题）的栈。在这个特定的问题中，我们使用的是递减栈。
• 具体来说，对于给定的温度列表 t，我们将遍历列表，如果当前温度小于等于栈顶元素对应的温度，就将当前温度的索引压入栈中，因为当前温度并不会使得栈顶元素变得更暖和。一旦遇到一个比栈顶温度更高的温度，我们就找到了栈顶元素需要等待的天数，因此我们将栈顶元素依次弹出，并更新它们所需要等待的天数。
• 通过这种方式，我们可以利用单调栈的性质，高效地找到每个元素需要等待多久才会有更暖和的温度的天数。
• 因此，单调栈在解决这类问题时非常高效，可以在一次线性扫描中找到解决方案，时间复杂度为 O(n)。

复杂度

        时间复杂度:

                O(n)

        时间复杂度为 O(n)，其中 n 是输入数组 t 的长度。这是因为我们最多对数组 t 中的每个元素进行一次入栈和一次出栈操作，而每次操作的时间复杂度都是 O(1)。

        空间复杂度

                O(n)

        空间复杂度为 O(n)，主要是由栈和结果数组所占用的空间决定的，它们的大小都与输入数组 t 的长度成线性关系。

c++ 代码

class Solution {
public:// 函数功能：返回每日温度列表 t 中，需要等待多久才会有更暖和的温度的天数vector<int> dailyTemperatures(vector<int>& t) {stack<int> st;  // 用栈来存储温度列表 t 的索引vector<int> ans(t.size(), 0);  // 初始化一个与 t 大小相同的结果向量，初始值为 0st.push(0);  // 将第一天的索引压入栈中for (int i = 1; i < t.size(); i++) {if (t[i] <= t[st.top()])  // 如果当前温度小于等于栈顶元素对应的温度st.push(i);  // 将当前索引压入栈中else {while (!st.empty() && t[i] > t[st.top()]) {  // 当栈不为空且当前温度大于栈顶元素对应的温度ans[st.top()] = i - st.top();  // 更新结果向量中栈顶索引对应的值为当前索引与栈顶索引的差值st.pop();  // 弹出栈顶元素}st.push(i);  // 将当前索引压入栈中}}return ans;  // 返回结果向量}
};

Java代码

class Solution {public int[] dailyTemperatures(int[] temperatures) {int lens = temperatures.length; // 获取温度数组的长度int[] res = new int[lens]; // 初始化结果数组Deque<Integer> stack = new LinkedList<>(); // 创建一个栈来保存温度数组的索引for (int i = 0; i < lens; i++) { // 遍历温度数组while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { // 如果栈不为空且当前温度大于栈顶温度res[stack.peek()] = i - stack.peek(); // 更新栈顶温度对应的等待天数stack.pop(); // 弹出栈顶温度}stack.push(i); // 将当前温度的索引压入栈中}return res; // 返回结果数组}
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。