503. Next Greater Element II(单调栈)

xiaoxiao2021-02-28  84

https://leetcode.com/problems/next-greater-element-ii/description/

题目: 给一个循环数组,返回一个等长的数组,数组中的每一个元素是:它后面的第一个大于它的元素(如果后面没有就循环一遍到最前面找,直到循环了一圈为止),如果不存在这样的数,就返回-1~

思路:

首先建立一个等长的vt数组,起始都是-1。这个题目要两个循环解决,第一个循环i从0~n-1,对于每一个nums[i],把他们的下标index都放入栈中。但是在放入栈之前需要做这样的事情:比较栈顶元素和nums[i],如果恰好比nums[i]小,说明nums[i]就是它的第一大元素,就将v[[s.top()]的值变为nums[i]

开始第二次循环,依旧i从0~n-1,处理栈中剩下的元素,对于nums[i],如果栈顶元素和nums[i]比较,恰好nums[i]大,说明nums[i]就是他们这些没在后面找到最大元素的最大元素,出栈,result[s.top()] = nums[i]。这样所有遍历完毕后栈中只会剩下唯一一个元素,也就是该数组中最大的元素,它的result依旧是-1,其他的都已经更新完毕。

代码

class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { vector<int>v(nums.size(),-1); stack<int>s; for(int x=0;x<nums.size();x++){ while(!s.empty()&&nums[x] > nums[s.top()]){ v[s.top()] = nums[x]; s.pop(); } s.push(x); } for(int x=0;x < nums.size();x++){ while(!s.empty()&&x < s.top()&&nums[x] > nums[s.top()]){ v[s.top()] = nums[x]; s.pop(); } } return v; } };
转载请注明原文地址: https://www.6miu.com/read-2250010.html

最新回复(0)