《代码随想录》刷题打卡day41：单调栈-part01

文章目录【739.每日温度】1. 怎么能想到用单调栈呢 什么时候用单调栈呢2. 那么单调栈的原理是什么呢为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢3. 在使用单调栈的时候首先要明确如下几点4. 举例分析【496.下一个更大元素】【503.下一个更大元素II】【739.每日温度】思路首先想到的当然是暴力解法两层for循环把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)那么接下来在来看看使用单调栈的解法。1. 怎么能想到用单调栈呢 什么时候用单调栈呢通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。时间复杂度为O(n)。例如本题其实就是找找到一个元素右边第一个比自己大的元素此时就应该想到用单调栈了。2. 那么单调栈的原理是什么呢为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢单调栈的本质是空间换时间因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次。更直白来说就是用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。3. 在使用单调栈的时候首先要明确如下几点单调栈里存放的元素是什么单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。单调栈里元素是递增呢 还是递减呢注意以下讲解中顺序的描述为 从栈头到栈底的顺序因为单纯的说从左到右或者从前到后不说栈头朝哪个方向的话大家一定比较懵。这里我们要使用递增循序再强调一下是指从栈头到栈底的顺序因为只有递增的时候栈里要加入一个元素i的时候才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。即如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。文字描述理解起来有点费劲接下来用一系列的图来讲解单调栈的工作过程。使用单调栈主要有三个判断条件。当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况把这三种情况分析清楚了也就理解透彻了。4. 举例分析接下来我们用temperatures [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。首先先将第一个遍历元素加入单调栈加入T[1] 74因为T[1] T[0]当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况。我们要保持一个递增单调栈从栈头到栈底所以将T[0]弹出T[1]加入此时result数组可以记录了result[0] 1即T[0]右面第一个比T[0]大的元素是T[1]。加入T[2]同理T[1]弹出加入T[3]T[3] T[2] 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况加T[3]加入单调栈。加入T[4]T[4] T[3] 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况此时依然要加入栈不用计算距离因为我们要求的是右面第一个大于本元素的位置而不是大于等于加入T[5]T[5] T[4] 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况将T[4]弹出同时计算距离更新resultT[4]弹出之后 T[5] T[3] 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况将T[3]继续弹出同时计算距离更新result直到发现T[5]小于T[st.top()]终止弹出将T[5]加入单调栈加入T[6]同理需要将栈里的T[5]T[2]弹出同理继续弹出此时栈里只剩下了T[6]加入T[7] T[7] T[6] 直接入栈这就是最后的情况result数组也更新完了。那result[6] , result[7]怎么没更新啊元素也一直在栈里。其实定义result数组的时候就应该直接初始化为0如果result没有更新说明这个元素右面没有更大的了也就是为0。以上在图解的时候已经把这三种情况都做了详细的分析。情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况通过以上过程大家可以自己再模拟一遍就会发现只有单调栈递增从栈口到栈底顺序就是求右边第一个比自己大的单调栈递减的话就是求右边第一个比自己小的。代码classSolution{public:vectorintdailyTemperatures(vectorinttemperatures){// 递增栈从栈头到栈底递增stackintst;vectorintresult(temperatures.size(),0);st.push(0);// 单调栈里只需要存放元素的下标ifor(inti1;itemperatures.size();i){if(temperatures[i]temperatures[st.top()]){st.push(i);}else{while(!st.empty()temperatures[i]temperatures[st.top()]){// 注意要先判断非空再取top不然一旦已经空了top()就会保存result[st.top()]i-st.top();st.pop();}st.push(i);}}returnresult;}};v【496.下一个更大元素】思路从题目示例中我们可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素那么就要定义一个和nums1一样大小的数组result来存放结果。nums1 是 nums2的子集找nums1中的元素在nums2中下一个比当前元素大的元素。这么定义这个result数组初始化应该为多少呢题目说如果不存在对应位置就输出 -1 所以result数组如果某位置没有被赋值那么就应该是是-1所以就初始化为-1。在遍历nums2的过程中我们要判断nums2[i]是否在nums1中出现过因为最后是要根据nums1元素的下标来更新result数组。注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。没有重复元素我们就可以用map来做映射了。根据数值快速找到下标还可以判断nums2[i]是否在nums1中出现过。C中当我们要使用集合来解决哈希问题的时候优先使用unordered_set因为它的查询和增删效率是最优的。那么预处理代码如下:unordered_mapint,intumap;// key:下标元素value下标for(inti0;inums1.size();i){umap[nums1[i]]i;}使用单调栈首先要想单调栈是从大到小还是从小到大。本题和739. 每日温度是一样的。**栈头到栈底的顺序要从小到大也就是保持栈里的元素为递增顺序。**只要保持递增才能找到右边第一个比自己大的元素。递减栈就是求右边第一个比自己小的元素了。接下来就要分析如下三种情况一定要分析清楚。情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况此时满足递增栈栈头到栈底的顺序所以直接入栈。情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候。判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。记录结果这块逻辑有一点小绕要清楚此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]即当前遍历元素。代码如下while(!st.empty()nums2[i]nums2[st.top()]){if(umap.count(nums2[st.top()])0){// 看map里是否存在这个元素intindexumap[nums2[st.top()]];// 根据map找到nums2[st.top()] 在 nums1中的下标result[index]nums2[i];}st.pop();}st.push(i);代码classSolution{public:vectorintnextGreaterElement(vectorintnums1,vectorintnums2){stackintst;vectorintresult(nums1.size(),-1);if(nums1.size()0)returnresult;unordered_mapint,intumap;// key:下标元素value下标for(inti0;inums1.size();i){umap[nums1[i]]i;}st.push(0);for(inti1;inums2.size();i){if(nums2[i]nums2[st.top()]){st.push(i);}else{while(!st.empty()nums2[i]nums2[st.top()]){if(umap.count(nums2[st.top()])0){// 看map里是否存在这个元素intindexumap[nums2[st.top()]];// 找到这个元素在nums1里的下标result[index]nums2[i];}st.pop();}st.push(i);}}returnresult;}};【503.下一个更大元素II】思路方法一将两个nums数组拼接在一起使用单调栈计算出每一个元素的下一个最大值最后再把结果集即result数组resize到原数组大小就可以了。代码如下// 版本一classSolution{public:vectorintnextGreaterElements(vectorintnums){// 拼接一个新的numsvectorintnums1(nums.begin(),nums.end());nums.insert(nums.end(),nums1.begin(),nums1.end());// 用新的nums大小来初始化resultvectorintresult(nums.size(),-1);if(nums.size()0)returnresult;// 开始单调栈stackintst;st.push(0);for(inti1;inums.size();i){if(nums[i]nums[st.top()])st.push(i);elseif(nums[i]nums[st.top()])st.push(i);else{while(!st.empty()nums[i]nums[st.top()]){result[st.top()]nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size()/2);returnresult;}};这种写法确实比较直观但做了很多无用操作例如修改了nums数组而且最后还要把result数组resize回去。resize倒是不费时间是O(1)的操作但扩充nums数组相当于多了一个O(n)的操作。方法二其实也可以不扩充nums而是在遍历的过程中模拟走了两边nums。代码如下// 版本二classSolution{public:vectorintnextGreaterElements(vectorintnums){vectorintresult(nums.size(),-1);if(nums.size()0)returnresult;stackintst;st.push(0);for(inti1;inums.size()*2;i){// 模拟遍历两边nums注意一下都是用i % nums.size()来操作if(nums[i%nums.size()]nums[st.top()])st.push(i%nums.size());elseif(nums[i%nums.size()]nums[st.top()])st.push(i%nums.size());else{while(!st.empty()nums[i%nums.size()]nums[st.top()]){result[st.top()]nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}returnresult;}};可以版本二不仅代码精简了也比版本一少做了无用功classSolution{public:vectorintnextGreaterElements(vectorintnums){vectorintresult(nums.size(),-1);if(nums.size()0)returnresult;stackintst;st.push(0);for(inti0;inums.size()*2;i){if(nums[i%nums.size()]nums[st.top()]){st.push(i%nums.size());}else{while(!st.empty()nums[i%nums.size()]nums[st.top()]){result[st.top()]nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}returnresult;}};