嘉祥做网站,wordpress刷量插件,什么叫展示型网站,title:(网站开发)下一个更大元素 II
给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序#xff0c;这个数字之后的第一个比它更大的数 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]思路 /* 单调栈 定义一个result用来存下标,和一个栈st用来存元素下标首先栈先存入数组的第一个元素从数组的第二个元素element开始比较 if(elementnums[st.top()]) st.push(i); else{ while(!st.empty()nums[i]nums[st.top()]){ result[st.top()] i; st.pop(); } st.push(i); } 对于循环搜索 for(int i 0;inums.size()*2;i)类似遍历两遍 i i%nums.size();求模不至于访问数组越界 */
代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {/*单调栈定义一个result用来存下标,和一个栈st用来存元素下标首先栈先存入数组的第一个元素从数组的第二个元素element开始比较if(elementnums[st.top()]) st.push(i);else{while(!st.empty()nums[i]nums[st.top()]){result[st.top()] i;st.pop();}st.push(i);}对于循环搜索for(int i 0;inums.size()*2;i)类似遍历两遍i i%nums.size();求模不至于访问数组越界*/vectorintresult(nums.size(),-1);stackintst;st.push(0);for(int i 1;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());}return result;}
};
42. 接雨水
给定 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思路 /* 采用单调栈 定义一个栈 用来存下标首先先把数组的第一个元素下标存入栈然后从数组的第二个元素开始遍历 遍历到的元素如果小于栈顶元素就把该元素的下标存入栈 遍历到的元素如果大于栈顶元素就把栈顶元素下标取出记录比该元素大的第一个元素的下标这个过程是持续性的过程。 以上就是单调栈 本题可以找到栈顶元素的比其右边大的元素即遍历到的元素左边遍历到的大的元素即栈顶的下一个元素 */
代码
class Solution {
public:int trap(vectorint height) {/*采用单调栈 定义一个栈 用来存下标首先先把数组的第一个元素下标存入栈然后从数组的第二个元素开始遍历遍历到的元素如果小于栈顶元素就把该元素的下标存入栈遍历到的元素如果大于栈顶元素就把栈顶元素下标取出记录比该元素大的第一个元素的下标这个过程是持续性的过程。以上就是单调栈本题可以找到栈顶元素的比其右边大的元素即遍历到的元素左边遍历到的大的元素即栈顶的下一个元素*/stackintst;st.push(0);int sum 0;for(int i 1;iheight.size();i){if(height[i]height[st.top()]){st.push(i);}else if(height[i]height[st.top()]){st.push(i);}else{while(!st.empty()height[i]height[st.top()]){int mid st.top();st.pop();if(!st.empty()){ int heigh min(height[i],height[st.top()])-height[mid];int width i-st.top()-1;sum heigh*width;}}}st.push(i);}return sum;}
};
还有很多瑕疵还需继续坚持
