題目
#

leetcode 503 - Next Greater Element II (題目說明請點連結)

題目簡述
#

給定一個循環數組，對於每個元素，找到下一個更大的元素。如果不存在下一個更大的元素，則輸出 -1。

範例
#

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: 對於每個元素，找到下一個更大的元素（可以循環查找）。

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
Explanation: 對於每個元素，找到下一個更大的元素（可以循環查找）。

解題思路
#

這題要求我們對於數組中的每個元素，找到下一個更大的元素。與 leetcode 496不同的是，這題的數組是循環的，也就是說可以從數組末尾回到開頭繼續查找下一個更大的元素。

解法
#

我們可以使用 stack 來解決這個問題。具體步驟如下：

使用 stack 來維護數組中的索引
初始化結果數組，所有元素設為 -1
遍歷數組兩次（模擬循環），對於每個元素，如果 stack 頂元素對應的值小於當前元素，則更新結果
只在第一次遍歷時將索引加入 stack

例子說明
#

nums = [1,2,1]

初始情況：stack = []，res = [-1, -1, -1]

第一次遍歷：
- i = 0, num = 1：stack 為空，將索引 0 入 stack
- i = 1, num = 2：stack 頂元素對應的值 1 < 2，更新 res[0] = 2，將索引 1 入 stack
- i = 2, num = 1：stack 頂元素對應的值 2 > 1，將索引 2 入 stack
第二次遍歷：
- i = 3, num = 1：stack 頂元素對應的值 1 = 1，將索引 0 入 stack
- i = 4, num = 2：stack 頂元素對應的值 1 < 2，更新 res[2] = 2
- i = 5, num = 1：stack 頂元素對應的值 2 > 1，將索引 1 入 stack
最終結果：
- res = [2, -1, 2]

完整程式碼
#

java

import java.util.*;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>(); // 使用stack來維護數組中的索引
        int n = nums.length, res[] = new int[n]; // 初始化結果數組
        Arrays.fill(res, -1); // 將所有結果設為-1

        // 遍歷數組兩次，模擬循環查找
        for (int i = 0; i < n * 2; i++) {
            int num = nums[i % n]; // 獲取當前元素（模擬循環）
            // 如果stack不為空且stack頂元素對應的值小於當前元素，則更新結果
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                res[stack.pop()] = num; // 更新stack頂元素的下一個更大元素
            }
            // 只在第一次遍歷時將索引加入stack
            if (i < n) {
                stack.push(i);
            }
        }
        return res;
    }
}