国外建设网站,中信建设有限责任公司待遇怎么样,金华建设网站的公司,建筑工程招聘最新信息平台算法学习——LeetCode力扣单调栈篇 739. 每日温度
739. 每日温度 - 力扣#xff08;LeetCode#xff09;
描述
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个…算法学习——LeetCode力扣单调栈篇 739. 每日温度
739. 每日温度 - 力扣LeetCode
描述
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例
示例 1:
输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures [30,60,90] 输出: [1,1,0]
提示
1 temperatures.length 105 30 temperatures[i] 100
代码解析
单调栈
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。
用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[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]弹出同时计算距离更新result T[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。
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()0 temperatures[i] temperatures[st.top()] ){result[st.top()] i - st.top();st.pop();}st.push(i);}return result;}
};496. 下一个更大元素 I
496. 下一个更大元素 I - 力扣LeetCode
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 [4,1,2], nums2 [1,3,4,2]. 输出[-1,3,-1] 解释nums1 中每个值的下一个更大元素如下所述
4 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。1 用加粗斜体标识nums2 [1,3,4,2]。下一个更大元素是 3 。2 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。
示例 2
输入nums1 [2,4], nums2 [1,2,3,4]. 输出[3,-1] 解释nums1 中每个值的下一个更大元素如下所述
2 用加粗斜体标识nums2 [1,2,3,4]。下一个更大元素是 3 。4 用加粗斜体标识nums2 [1,2,3,4]。不存在下一个更大元素所以答案是 -1 。
提示
1 nums1.length nums2.length 1000 0 nums1[i], nums2[i] 104 nums1和nums2中所有整数 互不相同 nums1 中的所有整数同样出现在 nums2 中
代码解析
和 739 完全一样
739是找每一个点的右边第一个大于点该题是找部分点num1的右边第一个最大点
具体步骤
用map记录num1出现的点然后和739一样找每一个右边第一个最大值找到后判断该点是否是num1里面的是就保存不是就放弃此处和739不同739找到就保存
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {vectorint result(nums1.size(),-1);stackint st;unordered_mapint,int umap;for(int i0 ; inums1.size(); i){umap[nums1[i]] i; }// for(auto it:umap) coutit.first it.secondendl;st.push(0);for(int i1 ;inums2.size();i){while(st.empty()0 nums2[i] nums2[st.top()]){if(umap.count(nums2[st.top()]) 0 ){int index umap[nums2[st.top()]];result[index] nums2[i];}st.pop();}st.push(i);}return result;}
};503. 下一个更大元素 II
503. 下一个更大元素 II - 力扣LeetCode
描述
给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
示例
示例 1:
输入: nums [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2 数字 2 找不到下一个更大的数 第二个 1 的下一个最大的数需要循环搜索结果也是 2。
示例 2:
输入: nums [1,2,3,4,3] 输出: [2,3,4,-1,4]
提示
1 nums.length 104 -109 nums[i] 109
代码解析
和496 类似为循环数组。将num数组扩充两倍连起来即可
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {vectorint result(nums.size(),-1);vectorint my_nums(nums.begin() , nums.end());stackint st;int indnx;// for(auto it:nums) my_nums.push_back(it); //循环插入my_nums.insert(my_nums.end(), nums.begin(), nums.end()); //insert插入st.push(0);for(int i1 ; imy_nums.size() ;i){while(st.empty()0 my_nums[i] my_nums[st.top()]){ //检测是否是第二圈if(st.top()nums.size()) indnx st.top() - nums.size();else indnx st.top();result[indnx] my_nums[i];st.pop();}st.push(i);}return result;}
};42. 接雨水
42. 接雨水 - 力扣LeetCode
描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 示例
示例 1
输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。
示例 2
输入height [4,2,0,3,2,5] 输出9
提示
n height.length 1 n 2 * 104 0 height[i] 105
代码解析
单调栈 从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了此时就出现凹槽了栈头元素就是凹槽底部的柱子栈头第二个元素就是凹槽左边的柱子而添加的元素就是凹槽右边的柱子。 遇到相同的元素更新栈内下标就是将栈里元素旧下标弹出将新元素新下标加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出把第二个5添加到栈中。
因为我们要求宽度的时候 如果遇到相同高度的柱子需要使用最右边的柱子来计算宽度。
单调栈处理逻辑 先将下标0的柱子加入到栈中 然后开始从下标1开始遍历所有的柱子 如果当前遍历的元素柱子高度小于栈顶元素的高度就把这个元素加入栈中因为栈里本来就要保持从小到大的顺序从栈头到栈底。 如果当前遍历的元素柱子高度等于栈顶元素的高度要跟更新栈顶元素因为遇到相相同高度的柱子需要使用最右边的柱子来计算宽度。 如果当前遍历的元素柱子高度大于栈顶元素的高度此时就出现凹槽了如图所示栈顶和栈顶的下一个元素以及要入栈的三个元素来接水
class Solution {
public:int trap(vectorint height) {if(height.size()2) return 0;stackint st;int result 0;st.push(0);for(int i1 ; iheight.size() ;i){//当前柱子比栈顶的小if(height[i] height[st.top()])st.push(i);//当前柱子和栈顶相等else if(height[i] height[st.top()]){st.pop();st.push(i);//当前柱子比栈顶的大产生了凹陷}else if(height[i] height[st.top()]){while(st.empty()0 height[i] height[st.top()]){int mid st.top();st.pop();if(st.empty()0) {int left st.top();int right i;int h min(height[left] , height[right]) - height[mid];int w right - left -1;result h*w;}}st.push(i);}}return result;}
};84. 柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣LeetCode
描述
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
示例
示例 1: 输入heights [2,1,5,6,2,3] 输出10 解释最大的矩形为图中红色区域面积为 10
示例 2 输入 heights [2,4] 输出 4
提示
1 heights.length 105 0 heights[i] 104
代码解析
单调栈
我们可以遍历每根柱子以当前柱子 i 的高度作为矩形的高那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体向右找到第一个高度小于当前柱体 i 的柱体。 和42接雨水类似 为什么这么说呢42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。 那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序 只有栈里从大到小的顺序才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。 所以本题单调栈的顺序正好与接雨水反过来。 此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
class Solution {
public:int largestRectangleArea(vectorint heights) {heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素stackint st;int result 0;st.push(0);for(int i1 ; iheights.size() ;i){if( heights[i] heights[st.top()] ) st.push(i);else if(heights[i] heights[st.top()]){st.pop();st.push(i);}else {while(st.empty()0 heights[i] heights[st.top()] ){int mid st.top();st.pop();if(st.empty()0){int left st.top();int right i;int sum (right - left -1) * heights[mid];coutleft mid right sumendl;if(sum result) result sum; }}st.push(i); }}return result;}
};
