[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++

Java

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

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

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

kotlin