代码随想录算法训练营第48天 | LeetCode739.每日温度、 LeetCode496.下一个更大元素I、 LeetCode503.下一个更大元素II

LeetCode739.每日温度

LeetCode496.下一个更大元素I

1. 暴力解法

2. 单调栈法

LeetCode503.下一个更大元素II

LeetCode739.每日温度

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

思路：这里涉及到了单调栈的问题。

当我们遇到要求某个元素最左边或者最右边第一个大于或小于该元素的值时，就可以考虑使用单调栈。

单调栈的本质就是拿空间换时间，使用一个栈来记录之前已经遍历过的元素，这样可以依据已经遍历过的元素来做出判断，得出结果。所以它的时间复杂度通常是O(n)。

单调栈又分为递增栈和递减栈。

所谓递增栈就是从栈顶到栈底的顺序，元素呈递增的状态，通常是用于求某元素右边第一个比其大的元素的值；而递减栈也是从栈顶到栈底的顺序，元素呈递减的状态，通常是用于求某元素右边第一个比其小的元素的值。

这里的每日温度就是单调栈比较经典的题目。

首先如果是暴力的解法，那么就是两层循环，一层记录当前待记录的元素，另一层开始遍历该元素后面的元素，遇到第一个比它大的就记录并停止循环。这个思路比较好想，当时毕竟是暴力解法，容易超限。

    vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> answer(temperatures.size(), 0);for(int i = 0; i < temperatures.size(); i ++){int max_index = i;for(int j = i + 1; j < temperatures.size(); j ++){if(temperatures[j] > temperatures[max_index]){max_index = j;break;//碰到大的值即可停止遍历了}}if(max_index != i) answer[i] = max_index - i;}return answer;   }

时间复杂度：O(n^2)

空间复杂度：O(n)

所以这里我们采用单调栈，这里采用的是递增栈，使用一个栈来记录已经遍历过的元素。

当栈元素不为空，并且存在元素大于栈顶元素时，开始记录，注意这里是一个while循环，因为遇到一个较大值可能不止是一个元素的右边第一个最大值，可能存在多个，所以要多次比较，并且每次比较完成即可pop掉相应元素。

这里详细考虑了三种情况，遍历元素小于栈顶元素、遍历元素等于栈顶元素以及遍历元素大于栈顶元素。

    vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> answer(temperatures.size(), 0);stack<int> max_index;//递增栈记录下标索引max_index.push(0);for(int i = 1; i < temperatures.size(); i ++){if(temperatures[i] < temperatures[max_index.top()]){//遍历元素小于栈里面的元素max_index.push(i);}else if(temperatures[i] == temperatures[max_index.top()]){//遍历元素等于栈里面的元素max_index.push(i);}else{//遍历元素大于栈里面的元素while(!max_index.empty() && temperatures[i] > temperatures[max_index.top()]){answer[max_index.top()] = i - max_index.top();max_index.pop();}max_index.push(i);}}return answer;   }

其实可以发现上面三种情况具有共同点，所以可以简化为下面的代码。

    vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> answer(temperatures.size(), 0);stack<int> max_index;//记录下标索引max_index.push(0);for(int i = 1; i < temperatures.size(); i ++){//当栈不为空并且temperatures[i]>temperatures[max_index.top()],开始计算下次最高温度出现在几天后while(!max_index.empty() && temperatures[i] > temperatures[max_index.top()]){int index = max_index.top(); max_index.pop();answer[index] = i - index;}max_index.push(i);}return answer;   }

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode496.下一个更大元素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] 是如上所述的 下一个更大元素 。

思路：这里有两种思路，可以尝试暴力解法以及单调栈方法。

1. 暴力解法

这里有两层循环，外层循环是nums1中的元素，内层循环是nums2中的元素，在nums2中找到nums1[i]的元素，然后开始向后遍历，找到第一个最大元素值，记录下来即可。

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size(), -1);//记录最终结果for(int i = 0; i < nums1.size(); i ++){for(int j = 0; j < nums2.size(); j ++){if(nums1[i] == nums2[j]){//在nums2中找到了nums1中的元素int index = j ++;//开始找寻在这个相同元素后面是否存在比这个元素大的值while(index < nums2.size()){if(nums2[index] > nums1[i]){ans[i] = nums2[index];break;}else{index ++;}}}}}return ans;}

时间复杂度：O(n^2)

空间复杂度：O(n)

2. 单调栈法

我们可以借鉴一下每日温度的思路。

这里同样是要判断遍历元素是否大于栈顶元素。但是在赋值之前还要判断遍历元素是否在nums1中出现过，因为主体循环肯定是在nums2进行的。

这里知道nums1、nums2中的元素是不相等的，所以想要判断元素是否存在在nums1中，那么可以使用哈希方法进行映射，这里选择unordered_map对值和下标进行映射。

所以在遇到遍历元素大于栈顶元素的时候，需要判断nums1中是否出现过这个栈顶元素，因为如果出现过，那么这个遍历元素就是它在nums2中第一个大于它的值，就可以进行记录了。

这里需要注意pop函数的位置，一定是在条件判断之外的，否则会造成死循环。

下面是详细的情况讨论的代码。

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size(), -1);//记录最终结果unordered_map<int, int> mp;for(int i = 0; i < nums1.size(); i ++){//将nums1中的元素映射到mp中mp[nums1[i]] = i;}stack<int> st;//递增栈st.push(0);//存放下标for(int i = 1; i < nums2.size(); i ++){if(nums2[i] < nums2[st.top()]){//遍历元素小于栈顶元素st.push(i);}else if(nums2[i] == nums2[st.top()]){//遍历元素等于栈顶元素st.push(i);}else{//遍历元素大于栈顶元素while(!st.empty() && nums2[i] > nums2[st.top()]){if(mp.find(nums2[st.top()]) != mp.end()){//首先在遇到大于的情况下，查看在nums1中是否出现过该元素//如果出现过则根据映射找到在nums1中的索引下标，然后在ans对应的下标位置为这个大于的值nums2[i]ans[mp[nums2[st.top()]]] = nums2[i];}st.pop();}st.push(i);}}return ans;}

下面是进行精简后的代码。

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size(), -1);unordered_map<int, int> mp;for(int i = 0; i < nums1.size(); i ++){mp[nums1[i]] = i;}stack<int> st;st.push(0);for(int i = 1; i < nums2.size(); i ++){while(!st.empty() && nums2[i] > nums2[st.top()]){if(mp.find(nums2[st.top()]) != mp.end()){ans[mp[nums2[st.top()]]] = nums2[i];}st.pop();//这里的pop需要放在条件判断之外，否则会出现死循环，最后超限}st.push(i);}return ans;}

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode503.下一个更大元素II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路：这道题相对于上一道题来说比较简单，跟每日温度比起来相似度极高。

这里唯一的不同在于nums是一个循环数组。

处理循环数组可以有两种思路：

第一种是将两个nums拼接在一起，然后求出所有元素的下一个更大元素的ans，最后得到结果后将ans裁剪为一半(大小为nums.size()),返回即可。但是这里涉及到扩充以及resize操作，增加了一些没必要的操作，所以不是首选，这里只是提供一种思路。

第二种是采用循环遍历，将遍历次数设置为2*nums.size()（当然遍历次数为2*nums.size()-2即能满足题意了），统计元素的下一个更大的元素，其他的跟每日温度其实基本上就是一样的了，最后当循环结束即可得到最终结果。

    vector<int> nextGreaterElements(vector<int>& nums) {int size = nums.size();//记录下nums的大小vector<int> ans(size, -1);//记录最终结果stack<int> st;st.push(0);for(int i = 1; i < 2 * size - 1; i ++){//这里将循环的次数变成了2*size-2,足够绕一圈了while(!st.empty() && nums[i % size] > nums[st.top()]){ans[st.top()] = nums[i % size];st.pop();}st.push(i % size);}return ans;}