做消费金融网站,七牛 wordpress插件,搜索引擎排名查询,自己做报名网站教程文章目录 503.下一个更大元素II思路代码实现 42. 接雨水思路代码实现 503.下一个更大元素II
题目链接
思路
这道题和下一个更大元素 I的不同之处在于这个查找是循环的。 循环直接可以用查找两次来解决#xff0c;所以题目步骤唯一不同的就是循环的终止位置。
for(int i1;i… 文章目录 503.下一个更大元素II思路代码实现 42. 接雨水思路代码实现 503.下一个更大元素II
题目链接
思路
这道题和下一个更大元素 I的不同之处在于这个查找是循环的。 循环直接可以用查找两次来解决所以题目步骤唯一不同的就是循环的终止位置。
for(int i1;inums.size()*2;i){while(!st.empty() nums[i % nums.size()] nums[st.top()]) {result[st.top()] nums[i % nums.size()];st.pop();}st.push(i%nums.size());
}代码实现
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {stackint st;vectorint result(nums.size(),-1);for(int i1;inums.size()*2;i){while(!st.empty() nums[i % nums.size()] nums[st.top()]) {result[st.top()] nums[i % nums.size()];st.pop();}st.push(i%nums.size());}return result;}
};42. 接雨水
题目链接
思路
这道题直接变成困难题愿意就是前面的题目都是找一边的最大值而这道题是找两边的最大值。其实意识到这一点这道题也没那么难了。 已经知道单调栈储存的元素是从栈头到栈底单调递增的元素。在遍历元素Height[i]和st.top()相比较时会出现三种情况
Height[i] 大于 Height[st.top()]Height[i] 等于 Height[st.top()]Height[i] 小于 Height[st.top()]
情况2和情况3和之前操作一样先把元素放入栈内保存着遍历寻找下一个比它大的元素。 而情况1表明找到了st.top()前比它大的元素位置而st.top()后比他大的元素位置就是它在栈内位置的下方元素那么这道题就迎刃而解了困难题也没有那么“困难”。
代码实现
class Solution {
public:int trap(vectorint height) {stackint st;int right;int left;int mid;int result0;st.push(0);for(int i1;iheight.size();i){while(!st.empty()height[st.top()]height[i]){righti;midst.top();st.pop();if(st.empty())break;else leftst.top();result(right-left-1)*(min(height[right],height[left])-height[mid]);}st.push(i);}return result;}
}
