当前位置：首页 > article >正文

代码随想录算法训练营第五十八天 | 739. 每日温度、496. 下一个更大元素 I

article 2024/11/20 11:41:59

739. 每日温度

题目链接：739. 每日温度

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

文章讲解/视频讲解：https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html

思路与实现

我似乎用单调栈做过这道题，根据回忆写一下思路吧~

从后往前遍历，用一个单调栈存储元素和它对应的下标，这个栈是从大到小存储的，即栈底比栈顶大。如果单调栈为空或者栈顶元素大于当前遍历的值，则将当前遍历的值存入单调栈中。如果栈顶元素小于等于当前遍历的值，则弹出栈顶，直到单调栈为空或者栈顶元素大于当前遍历值为止。

在当前元素加入单调栈时，如果单调栈为空，那么说明没有下一个更高温度，结果用0表示；如果单调栈非空，结果为栈顶的下标减去当前元素的下标。代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int,int>> stk;
        vector<int> result(temperatures.size(), 0);
        for(int i = temperatures.size() - 1;i >= 0;i--){
            while(!stk.empty() && stk.top().second <= temperatures[i]){
                stk.pop();
            }
            if(stk.empty()) result[i] = 0;
            else result[i] = stk.top().first - i;
            stk.push({i, temperatures[i]});
        }
        return result;
    }
};

也可以让栈只存储元素下标，存储一个pair是没必要的。

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

看了卡哥的教程，也可以从前向后遍历，单调栈为从大到小。然后每次记录result[stk.top]的值。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        vector<int> result(temperatures.size(), 0);
        for(int i = 0;i<temperatures.size();i++){
            while(!stk.empty() && temperatures[stk.top()] < temperatures[i]){
                result[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return result;
    }
};

496. 下一个更大元素 I

题目链接：496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置右侧的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

文章讲解/视频讲解：https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html

思路与实现

首先对于nums2，用单调栈求出每个下标位置下一个更大元素。

根据题设，nums1、nums2中所有整数互不相同。因此可以用一个hashmap来存储nums2中所有整数的值和它对应的下标。接着遍历nums1数组，通过hashmap找到在nums2中对应的位置，再根据上一步得出下一个更大元素。

代码如下：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> stk;
        vector<int> nextNum(nums2.size(), -1);
        unordered_map<int,int> hashMap;
        for(int i = 0;i<nums2.size();i++){
            while(!stk.empty() && nums2[stk.top()] < nums2[i]){
                nextNum[stk.top()] = nums2[i];
                stk.pop();
            }
            stk.push(i);
            hashMap[nums2[i]] = i;
        }

        vector<int> result(nums1.size(), -1);
        for(int i = 0;i<nums1.size();i++){
            int idx = hashMap[nums1[i]];
            result[i] = nextNum[idx];
        }
        return result;
    }
};