宁波网站建设哪里有,深圳企业网站建设电话,开发app需要的技术,wordpress 4.7 主题503. 下一个更大元素 II#xff08;中等#xff09; 方法#xff1a;单调栈
「 对于找最近一个比当前值大/小」的问题#xff0c;都可以使用单调栈来解决。栈可以很好的保存原始位置#xff0c;最近影射栈顶。题目要求更大#xff0c;因此更大即解–出栈#xff0c;更小…503. 下一个更大元素 II中等 方法单调栈
「 对于找最近一个比当前值大/小」的问题都可以使用单调栈来解决。栈可以很好的保存原始位置最近影射栈顶。题目要求更大因此更大即解–出栈更小则入栈。「 栈内存放的永远是还没更新答案的下标。⌟
思路 首先创建一个大小为n的答案数组ans初始化为-1。 然后使用一个栈s来存储数组中的索引。 从数组的第一个元素开始遍历将第一个元素的索引压入栈中。 接着遍历数组的剩余元素。对于每个元素我们将栈顶元素与当前元素进行比较。 如果栈顶元素小于当前元素则说明栈顶元素的下一个更大元素就是当前元素。 我们将栈顶元素的下一个更大元素设置为当前元素并将栈顶元素出栈。 重复这个过程直到栈为空或者栈顶元素不小于当前元素。 最后将当前元素的索引压入栈中以便在后面的元素中找到它的下一个更大元素。 当遍历完整个数组后我们就得到了所有元素的下一个更大元素。 两次遍历由于目标要么在当前元素之前要么在之后因此两次遍历一定能覆盖到。
代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint ans(n, -1);// vectorint flag(n, 0);stackint s;s.push(0);for(int i1;i 2*n-2;i){while(!s.empty() (nums[s.top()] nums[i%n])){ans[s.top()] nums[i%n];s.pop();}s.push(i%n);}return ans;}
};
