[LeetCode]Next Greater Element II

和Next Greater Element I的区别就是array变成了环状，解法仍然是类似的。如果我们只从右向左扫一遍的话，是不够的。因为可能满足条件的数在当前数nums[i]的左边，我们只需要保持stack的状态，在从右向左扫一遍即可。时间复杂度O(n)，空间复杂度O(n)。代码如下：

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	int len = nums.size(), maxIdx = -1;
	vector<int> next(len);
	stack<int> st;
	for(int i = 0; i < 2 * len; ++i)
	{
	int idx = (len - i + len) % len;
	while(st.size() && st.top() <= nums[idx])st.pop();
	next[idx] = st.empty()? -1: st.top();
	st.push(nums[idx]);
	}
	return next;
	}
	};

view raw Next Greater Element II_1.cpp hosted with ❤ by GitHub

另一种做法，我们找到nums当中的最大数max，然后从max开始从右向左round-robin式地扫一遍就行了。应为max可以当做绝对的右边界，所有的数，要么在其或者其之前的位置找到答案，要不不存在答案。时间复杂度O(n)，空间复杂度O(n)。代码如下：

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	int len = nums.size(), maxIdx = -1;
	if(!len)return {};
	for(int i = 0; i < len; ++i)
	maxIdx = maxIdx == -1? i : nums[i] > nums[maxIdx]? i : maxIdx;
	vector<int> next(len);
	next[maxIdx] = -1;
	stack<int> st;
	for(int i = 0; i < len; ++i)
	{
	int idx = (maxIdx - i + len) % len;
	while(st.size() && st.top() <= nums[idx])st.pop();
	next[idx] = st.empty()? -1: st.top();
	st.push(nums[idx]);
	}
	return next;
	}
	};

view raw Next Greater Element II_2.cpp hosted with ❤ by GitHub