代码随想录算法训练营
Day48 代码随想录算法训练营第 48 天 |LeetCode 739. 每日温度 LeetCode496.下一个更大元素 I LeetCode503.下一个更大元素II
目录
前言
LeetCode 739. 每日温度
LeetCode496.下一个更大元素 I
LeetCode503.下一个更大元素II
一、基础
1、栈内存放下标
2、应用：找元素右边第一个大于/小于他的元素
3、找元素右边第一个大于他的元素
（1）a[0]:将0放入栈
（2）a[i]:
1）如果栈空：i入栈
2）如果栈顶对应元素大于等于a[i]:i入栈
3）栈顶对应元素小于a[i]：（while循环控制边界）
① a[i]就是栈顶对应元素右边第一个大于他的元素，记录答案
② 弹出栈顶
③ i入栈
二、LeetCode 739. 每日温度
1.题目链接
2.思路
1）a[0]:将0放入栈
（2）a[i]:
1）如果栈空：i入栈
2）如果栈顶对应元素大于等于a[i]:i入栈
3）栈顶对应元素小于a[i]：（while循环控制边界）
① a[i]就是栈顶对应元素右边第一个大于他的元素，记录答案---- i-s.top()
② 弹出栈顶
③ i入栈
3.题解
class Solution {
public:
stack<int> s;
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
s.push(0);
for (int i = 1; i < n; i++) {
if (s.size() == 0)
s.push(i);
else {
if (temperatures[s.top()] >= temperatures[i]) {
s.push(i);
} else {
while (!s.empty() &&
temperatures[s.top()] < temperatures[i]) {
res[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
}
}
return res;
}
};
三、LeetCode496.下一个更大元素
1.题目链接
2.思路
问题转换：
问题转换成：同时属于nums1和nums2的元素在nums2中右边第一个比自己大的元素下标
方法一：
（1）单调栈存放待处理的元素下标：
单调栈存放nums2的元素在Nums2中下标（但是真正对答案有用的是同时属于nums1和nums2的元素）
（2）过程
1）为了通过同时属于nums1和nums2的元素值找在nums1中的下标，用映射，元素为key，下标为values
2）单调栈
① 下标0放入
② 栈空或栈顶元素>=nums2[i]：入栈
③ 栈顶元素<nums2[i]:
如果栈顶元素在nums1出现，那么栈顶元素在nums1中对应元素的答案是nums2[i]
无论栈顶元素是否在nums1出现，弹出栈顶
跳出循环后i入栈
方法二：
1）单调栈存放待处理的元素下标：
单调栈存放同时属于nums1和nums2的元素在Nums2中下标
（2）过程
1）为了通过同时属于nums1和nums2的元素值找在nums1中的下标，用映射，元素为key，下标为values
2）单调栈
① 栈空或栈顶元素>=nums2[i]：如果nums2[i]在nums1出现，i入栈
③ 栈顶元素<nums2[i]:
栈顶元素在nums1中对应元素的答案是nums2[i]
弹出栈顶
跳出循环后，如果nums2[i]在nums1出现，i入栈
3.题解
方法1
class Solution {
public:
stack<int>s;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int n1=nums1.size();
int n2=nums2.size();
vector<int>res(n1,-1);
s.push(0);
unordered_map<int,int>map;
for(int i=0;i<n1;i++){
map[nums1[i]]=i;
}
for(int i=1;i<n2;i++)
{
if(s.size()==0 || nums2[s.top()]>=nums2[i])s.push(i);
else
{
while(!s.empty()&&nums2[s.top()]<nums2[i])
{
if(map.count(nums2[s.top()]) > 0)
res[map[nums2[s.top()]]]=nums2[i];
s.pop();
}
s.push(i);
}
}
return res;
}
};
方法2
class Solution {
public:
stack<int> s;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<int> res(n1, -1);
unordered_map<int, int> map;
for (int i = 0; i < n1; i++) {
map[nums1[i]] = i;
}
for (int i = 0; i < n2; i++) {
if ((s.size() == 0 || nums2[s.top()] >= nums2[i]) &&
map.count(nums2[i]) > 0) {
s.push(i);
} else {
while (!s.empty() && nums2[s.top()] < nums2[i]) {
res[map[nums2[s.top()]]] = nums2[i];
s.pop();
}
if (map.count(nums2[i]) > 0)
s.push(i);
}
}
return res;
}
};
四、LeetCode503.下一个更大元素II
1.题目链接
2.思路
（1）审题：循环数组
e.g.输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2
（2）为了确保每个元素都能搜索完一个周期：从0到2n-1遍历
（相当于将数组扩增：abd—abdabd）
3.题解
class Solution {
public:
stack<int> s;
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
for (int i = 0; i < n * 2; i++) {
if (s.empty() || nums[s.top()] >= nums[i % n])
s.push(i % n);
else {
while (!s.empty() && nums[s.top()] < nums[i % n]) {
res[s.top()] = nums[i % n];
s.pop();
}
s.push(i % n);
}
}
return res;
}
};
标签：栈顶,top,元素,随想录,vector,更大,nums1,nums2 From： https://blog.csdn.net/2301_79647020/article/details/141337562