企业网站建设上市公司,网站怎么做现场直播视频,公众号排名优化,微信小程序开发教程官方文档题目1#xff1a;739 每日温度
题目链接#xff1a;每日温度
对题目的理解
temperature[i]表示每天的温度#xff0c;返回数组answer#xff0c;answer[i]指对于第i天#xff0c;下一个更高温度最近出现在几天后#xff0c;如果气温在这之后都不会升高#xff0c;用0…题目1739 每日温度
题目链接每日温度
对题目的理解
temperature[i]表示每天的温度返回数组answeranswer[i]指对于第i天下一个更高温度最近出现在几天后如果气温在这之后都不会升高用0来代替
暴力解法
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint answer(temperatures.size(),0);for(int i0;itemperatures.size();i){for(int ji1;jtemperatures.size();j){if(temperatures[j]temperatures[i]){answer[i]j-i;break;} }}return answer;}
};
会报超时错误 单调栈
1何时想到使用单调栈
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了时间复杂度为O(n)。
单调栈的本质是空间换时间因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次。
就是用一个栈来记录已经遍历过的元素
2如何使用单调栈
单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。
只有递增的时候栈里要加入一个元素i的时候才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
使用单调栈主要有三个判断条件。
当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
整个流程 定义result数组的时候就应该直接初始化为0如果result没有更新说明这个元素右面没有更大的了也就是为0。
伪代码 代码
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint result(temperatures.size(),0);stackint st;st.push(0);for(int i1;itemperatures.size();i){if(temperatures[i]temperatures[st.top()]) st.push(i);else if(temperatures[i]temperatures[st.top()]) st.push(i);else {while(!st.empty() temperatures[i]temperatures[st.top()]){result[st.top()] i-st.top();st.pop();}st.push(i);}}return result; }
};
时间复杂度O(n)空间复杂度O(n)
精简代码
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint result(temperatures.size(),0);stackint st;st.push(0);for(int i1;itemperatures.size();i){while(!st.empty() temperatures[i]temperatures[st.top()]){result[st.top()]i-st.top();st.pop();}if(temperatures[i]temperatures[st.top()]) st.push(i);}return result; }
};
上述代码会出现如下错误 原因是for循环中下面的if判断并没有限制st若st可能出现空栈的情况
将代码改正如下
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint result(temperatures.size(),0);stackint st;st.push(0);for(int i1;itemperatures.size();i){while(!st.empty() temperatures[i]temperatures[st.top()]){result[st.top()]i-st.top();st.pop();}if(!st.empty() temperatures[i]temperatures[st.top()]) st.push(i);}return result; }
};
这个时候倒是不报执行错误了又有新的错误产生了案例错误 出现这种错误的原因是在while循环中栈外元素大于栈顶元素的情况在栈顶元素弹出之后并没有将新的元素放入堆栈因此将代码修改如下
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint result(temperatures.size(),0);stackint st;st.push(0);for(int i1;itemperatures.size();i){while(!st.empty() temperatures[i]temperatures[st.top()]){result[st.top()]i-st.top();st.pop();st.push(i);}if(!st.empty() temperatures[i]temperatures[st.top()]) st.push(i);}return result; }
};
又有新的错误出现了 原因是while循环代表着栈外元素一直比栈顶元素大那么一直弹出栈顶元素直到小于等于为止这个过程不应该将栈外元素放入堆栈将栈外元素放入堆栈的操作应在整个while循环都遍历完成后才进行因此可以将代码改为如下因为栈外元素大于等于栈顶元素的时候一定是要放入堆栈的所以这两步操作可以合并起来就是没有这个if限制条件了只要不满足栈外元素大于栈顶元素了就将栈外元素放入堆栈这时代码才可以正常通过·
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {vectorint result(temperatures.size(),0);stackint st;st.push(0);for(int i1;itemperatures.size();i){while(!st.empty() temperatures[i]temperatures[st.top()]){result[st.top()]i-st.top();st.pop();}st.push(i);}return result; }
};
题目2496 下一个更大元素Ⅰ
题目链接下一个更大元素Ⅰ
对题目的理解
两个数组nums1和nums2无重复元素nums1是nums2的子集找满足nums1[i]nums2[j]的下标j即在数组nums2中找出与nums1中相同元素的下标并在nums2确定nums2[j]的下一个更大元素如果不存在则返回1
nums1中x的下一个更大元素是指x在nums2中对应位置右侧的第一个比x大的元素
nums1和nums2至少包含一个元素
常规思路
常规思路求出nums1中的元素在nums2中相等的下标然后根据这个下标数组遍历nums2进行查找但是卡死了一直报错误
代码卡死了
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { vectorint index(nums1.size(),0);for(int i0;inums1.size();i){for(int j0;jnums2.size();j){if(nums1[i]nums2[j]) index.push_back(j);}//使用index存储nums2中的下标4,7,8,9}vectorint result(nums1.size(),-1);stackint st;for(int i0;iindex.size();i){while(!st.empty() nums2[index[i]]nums2[st.top()]){result[]nums2[index[i]];st.pop();}st.push(index[i]);}return result;}
};
单调栈
注意题目中说是两个没有重复元素 的数组 nums1 和 nums2没有重复元素就可以用map来做映射了。根据数值快速找到下标还可以判断nums2[i]是否在nums1中出现过C中使用集合来解决哈希问题的时候优先使用unordered_set因为它的查询和增删效率是最优的 分析如下三种情况
情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况此时满足递增栈栈头到栈底的顺序所以直接入栈。
情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况如果相等的话依然直接入栈求的是右边第一个比自己大的元素而不是大于等于
情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。
伪代码 代码注意一定要是nums2[st.top()]
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { vectorint result(nums1.size(),-1);//初始化为-1stackint st;//定义一个哈希表来映射nums1的元素与下标的关系unordered_mapint,int umap;for(int i0;inums1.size();i){umap[nums1[i]]i;//元素 位置后续nums2根据与nums1中相同的元素找到该位置i,更新该处的数值}st.push(0);for(int i1;inums2.size();i){while(!st.empty() nums2[i]st.top()){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(st.top())0){int indexumap[st.top()];//获取这个元素在的位置最上面for循环的iresult[index]nums2[i];}st.pop();}st.push(nums2[i]);}return result;}
};
注意st栈中放的是下标是下标是下标重要的事情说三遍使用的时候需要将该下标带入数组一定要是nums2[st.top()]将代码改为如下就OK
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { vectorint result(nums1.size(),-1);//初始化为-1stackint st;//定义一个哈希表来映射nums1的元素与下标的关系unordered_mapint,int umap;for(int i0;inums1.size();i){umap[nums1[i]]i;//元素 位置后续nums2根据与nums1中相同的元素找到该位置i,更新该处的数值}st.push(0);for(int i1;inums2.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()]){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(nums2[st.top()])0){int indexumap[nums2[st.top()]];//获取这个元素在的位置最上面for循环的iresult[index]nums2[i];}st.pop();}st.push(i);}}return result;}
};
精简代码
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { vectorint result(nums1.size(),-1);//初始化为-1stackint st;//定义一个哈希表来映射nums1的元素与下标的关系unordered_mapint,int umap;for(int i0;inums1.size();i){umap[nums1[i]]i;//元素 位置后续nums2根据与nums1中相同的元素找到该位置i,更新该处的数值}st.push(0);for(int i1;inums2.size();i){while(!st.empty() nums2[i]nums2[st.top()]){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(nums2[st.top()])0){int indexumap[nums2[st.top()]];//获取这个元素在的位置最上面for循环的iresult[index]nums2[i];}st.pop();}st.push(i);}return result;}
};
