[LeetCode] 503. Next Greater Element II

轉自LeetCode

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won't exceed 10000.

<Solution>

這題是 496. Next Greater Element I 的衍生題

不同的地方在於，這次是 circular array

想法如下

• 一樣用 stack 來輔助，這次從 array 的尾端往開頭方向開始。因為會有重複數字出現，這次stack 存的是 index

• 如果下一個數字比目前 stack.top所在的數字大，代表 stack.top 所在的數字不是下一個數字的 next greater element，直接將 stack.top 給 pop 掉，重複直到下一個數字比目前 stack.top 所在的數字小為止

• 如果 stack 為空，目前這個位置的答案先填 -1；如果 stack 不為空，就填 stack.top

• 將目前的數字的 index 放到 stack 裡

• 這題的關鍵在於，要上面四個步驟總共要做兩次，這是為了符合 circular array 的特性。因為當做完第一次後，將 stack 保留的值，再重新和 nums 做比較，也就是將 nums 頭尾接起來，再比較一次的意思

code 如下

C++

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	const int len = nums.size();
	vector<int> ans(len);
	stack<int> stack;
	int index;
	//>> go through nums 2-pass to statisfy circular array condition
	for(int i = len * 2 - 1; i >= 0; i--) {
	index = i % len;
	while(!stack.empty() && nums[index] >= nums[stack.top()]) {
	stack.pop();
	}
	ans[index] = stack.empty() ? -1 : nums[stack.top()];
	stack.push(index);
	}
	return ans;
	}
	};

view raw nextGreaterElement2.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int[] nextGreaterElements(int[] nums) {
	Stack<Integer> stack = new Stack<>();
	int[] ans = new int[nums.length];
	int index;
	//>> go through nums 2-pass to statisfy circular array condition
	for(int i = nums.length * 2 - 1; i >= 0; i--) {
	index = i % nums.length;
	while(!stack.empty() && nums[index] >= nums[stack.peek()]) {
	stack.pop();
	}
	ans[index] = stack.empty() ? -1 : nums[stack.peek()];
	stack.push(index);
	}
	return ans;
	}
	}

view raw nextGreaterElement2.java hosted with ❤ by GitHub

同樣想法，只是作法不同，這次把 nums 重複一次後再來做

舉例，nums = [1,2,1]，變成 longerNums = [1,2,1,1,2,1]

然後一樣用 stack 來找 next great number 即可

kotlin

	class Solution {
	fun nextGreaterElements(nums: IntArray): IntArray {
	val longerNums = IntArray(nums.size*2)
	for(i in nums.indices) {
	longerNums[i] = nums[i]
	longerNums[nums.size+i] = nums[i]
	}
	val nextGreatNumber = IntArray(longerNums.size)
	val stack = mutableListOf<Int>()
	for(i in longerNums.lastIndex downTo 0) {
	while(stack.isNotEmpty() && longerNums[i] >= stack.last()) {
	stack.removeAt(stack.lastIndex)
	}
	nextGreatNumber[i] = if(stack.isEmpty()) -1 else stack.last()
	stack.add(longerNums[i])
	}
	return nextGreatNumber.take(nums.size).toIntArray()
	}
	}

view raw next_greater_element_II.kt hosted with ❤ by GitHub