題目
#

leetcode 496 - Next Greater Element I (題目說明請點連結)

題目簡述
#

對於 nums1 中的每個元素，找到 nums2 中該元素右側的第一個比它大的元素。

範例
#

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 對於 nums1 中的每個元素，在 nums2 中找到下一個更大的元素。

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: 對於 nums1 中的每個元素，在 nums2 中找到下一個更大的元素。

解題思路
#

這題要求我們對於 nums1 中的每個元素，在 nums2 中找到該元素右側第一個比它大的元素。如果沒有找到，則返回 -1。

解法
#

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

使用stack來維護 nums2 中的元素
使用 HashMap 來存儲每個元素的下一個更大元素
遍歷 nums2，對於每個元素，如果stack頂元素小於當前元素，則更新 HashMap
最後根據 nums1 中的元素從 HashMap 中獲取結果

例子說明
#

nums1 = [4,1,2], nums2 = [1,3,4,2]

初始情況：stack = []，map = {}

處理元素 1：
- stack為空，直接將 1 入stack
- stack = [1]
處理元素 3：
- stack頂元素 1 < 3，將 1 出stack並記錄 map[1] = 3
- stack為空，將 3 入stack
- stack = [3]，map = {1: 3}
處理元素 4：
- stack頂元素 3 < 4，將 3 出stack並記錄 map[3] = 4
- stack為空，將 4 入stack
- stack = [4]，map = {1: 3, 3: 4}
處理元素 2：
- stack頂元素 4 > 2，直接將 2 入stack
- stack = [4, 2]，map = {1: 3, 3: 4}
最終結果：
- 對於 nums1[0] = 4：map 中沒有 4，返回 -1
- 對於 nums1[1] = 1：map[1] = 3
- 對於 nums1[2] = 2：map 中沒有 2，返回 -1
- 結果：[-1, 3, -1]

完整程式碼
#

java

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>(); // 使用stack來維護nums2中的元素
        HashMap<Integer, Integer> map = new HashMap<>(); // 存儲每個元素的下一個更大元素

        // 遍歷nums2，使用單調stack找出每個元素的下一個更大元素
        for (int nums : nums2) {
            // 如果stack不為空且stack頂元素小於當前元素，則更新map
            while (!stack.isEmpty() && stack.peek() < nums) {
                map.put(stack.pop(), nums); // 將stack頂元素出stack並記錄其下一個更大元素
            }
            stack.push(nums); // 將當前元素入stack
        }

        // 根據nums1中的元素從map中獲取結果
        int[] res = new int[nums1.length];
        for (int i = 0; i < res.length; i++) {
            // 如果map中存在該元素的下一個更大元素，則返回該值，否則返回-1
            res[i] = map.containsKey(nums1[i]) ? map.get(nums1[i]) : -1;
        }

        return res;
    }
}