代码练习营 day52|LeetCode 739，LeetCode 496，LeetCode 503

前言

这里记录一下陈菜菜的刷题记录，重要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕，一年车企软件开发经验
代码能力：有待提高
常用语言：C++
系列文章目次

第52天 ：第十章 单调栈part01

---

`

  

---

---

一、本日任务

● 739. 每日温度
● 496.下一个更大元素 I
● 503.下一个更大元素II
二、具体布置

单调栈

使用场景

通常是一维数组，要寻找任一个元素的右边大概左边第一个比自己大大概小的元素的位置，此时我们就要想到可以用单调栈了。
时间复杂度为O(n)。
算法思绪

单调栈的本质是空间换时间，由于在遍历的过程中必要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只必要遍历一次。更直白来说，就是用一个栈来记录我们遍历过的元素。
1.单调栈里存放的元素是什么？
单调栈里只必要存放元素的下标i就可以了，如果必要使用对应的元素，直接T就可以获取。
2.单调栈里元素是递增呢？ 还是递减呢？
从栈头到栈底，视环境而定。
使用单调栈重要有三个判断条件
当前遍历的元素T小于栈顶元素T[st.top()]的环境
当前遍历的元素T等于栈顶元素T[st.top()]的环境
当前遍历的元素T大于栈顶元素T[st.top()]的环境
739. 每日温度

   标题链接：力扣739
文章讲解：代码随想录
  给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
提示：

1 <= temperatures.length <= 105
30 <= temperatures <= 100
样例1：

1. 输入: temperatures = [73,74,75,71,69,72,76,73]
2. 输出: [1,1,4,2,1,1,0,0]

复制代码

思绪

这题暴力很轻易想，但是会时间超限
实战

1. class Solution {
2. public:
3.     vector<int> dailyTemperatures(vector<int>& temperatures) {
4.         vector<int> result(temperatures.size(),0);
5.         /*for(int i=0;i<temperatures.size();i++){
6.             for(int j=i+1;j<temperatures.size();j++){
7.                 if(temperatures[j]>temperatures[i]){
8.                     result[i]=j-i;
9.                     break;
10.                 }
11.             }
12.         }*/
13.         stack<int> st;
14.         //st.push(0);
15.         for(int i=0;i<temperatures.size();i++){
16.             while(!st.empty() && temperatures[i]>temperatures[st.top()]){
17.                 result[st.top()]=i-st.top();
18.                 st.pop();
19.             }
20.             st.push(i);
21.         }
22.         return result;
23.     }
24. };

复制代码

496.下一个更大元素 I

   标题链接：力扣496题链接
文章讲解：图文讲解
  nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1 == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans 是如上所述的 下一个更大元素 。
提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1, nums2 <= 104
nums1和nums2中全部整数 互不相同
nums1 中的全部整数同样出现在 nums2 中
样例1：

1. 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
2. 输出：[-1,3,-1]
3. 解释：nums1 中每个值的下一个更大元素如下所述：
4. - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
5. - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
6. - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。   

复制代码

思绪

这题还挺绕的，关键是用map来实现通过数组元素找下标。
实战

1. class Solution {
2. public:
3.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
4.         vector<int> result(nums1.size(),-1);
5.         //vector<int> vec(nums2.size(),-1);
6.         stack<int> st;
7.         unordered_map<int, int> umap; // key:下标元素，value：下标,实现根据元素找下标
8.         for (int i = 0; i < nums1.size(); i++) {
9.             umap[nums1[i]] = i;
10.         }
11.         st.push(0);
12.         for(int i=1;i<nums2.size();i++){
13.             while(!st.empty() && nums2[st.top()]<nums2[i]){
14.                 if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
15.                     int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
16.                     result[index] = nums2[i];
17.                 }
18.                 st.pop();
19.             }
20.             st.push(i);
21.         }
22.         
23.         return result;
24.     }
25. };

复制代码

踩坑

用map能很好地实现互查。
503.下一个更大元素II

   标题链接：LeetCode503
文章讲解：图文讲解
  标题形貌
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历次序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
提示：

1 <= nums.length <= 104
-109 <= nums <= 109
样例1：

1. 输入: nums = [1,2,1]
2. 输出: [2,-1,2]
3. 解释: 第一个 1 的下一个更大的数是 2；
4. 数字 2 找不到下一个更大的数；
5. 第二个 1 的下一个最大的数需要循环搜索，结果也是 2

复制代码

样例2：

1. 输入: nums = [1,2,3,4,3]
2. 输出: [2,3,4,-1,4]

复制代码

思绪

这题跟第一题一样，区别在于循环，只要加一个取模就行，数组最多循环两遍就能出效果。
实战

1. class Solution {
2. public:
3.     vector<int> nextGreaterElements(vector<int>& nums) {
4.         stack<int> st;
5.         vector<int> result(nums.size(),-1);
6.         for(int i=0;i<nums.size()*2;i++){
7.             while(!st.empty() && nums[i%nums.size()]>nums[st.top()]){
8.                 result[st.top()]=nums[i%nums.size()];
9.                 st.pop();
10.             }
11.             st.push(i%nums.size());
12.         }
13.         return result;
14.     }
15. };

复制代码

总结

今天重要学习了单调栈的一系列操作，今天标题难度还行。
加油，坚持打卡的第52天。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。