Tech Base

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Note:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

 

難度簡單的題目，直接照字面上處理

首先新建一個陣列用來儲存結果，接著根據第一個陣列數字找到該數字在第二個陣列的位置，再用此數字與第二個陣列位置右側的所有數字做比較，若都比較小或是該數字位置已經是陣列最後一個則儲存 -1，若比較大就儲存該數字

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] newArr = new int[nums1.length];
        
        for(int i=0; i<nums1.length; i++) {
            newArr[i] = getGreaterNum(nums2, nums1[i]);
        }
        
        return newArr;
    }
    
    private int getGreaterNum(int[] nums, int target) {
        boolean flag = false;
        for(int i=0; i<nums.length; i++) {
            if(nums[i] == target && i != nums.length-1) {
                flag = true;
            }
            
            if(flag && nums[i] > target) {
                return nums[i];
            }
        }
        
        return -1;
    }
}

---

LeetCode 討論區中其他人的解法

假設有一數列為遞減 [5, 4, 3, 2, 1, 6] 則所有 6 前面的數字的 greater number 都是 6，若數列為 [7, 8, 9, 5, 4, 3, 2, 1, 6]，則可視為 [7, 8, 9] 和 [5, 4, 3, 2, 1, 6] ，根據前面則可以確定 7, 8 的 greater number 為 9，1-5 則是 6，要做到這點則可以用利用 stack

首先若 stack 為空或是目前數字比 stack 中的數字小時，將數字存入 stack 中，若否，則將 stack 中的數值取出並與其對應的 greater number 存入 map 中，最後再一次取出，即可得到答案

(此方法為 O(n) 而我自己寫的會是 O(n^2)。)

public int[] nextGreaterElement(int[] findNums, int[] nums) {
    Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
    Stack<Integer> stack = new Stack<>();
    for (int num : nums) {
        while (!stack.isEmpty() && stack.peek() < num)
            map.put(stack.pop(), num);
        stack.push(num);
    }   
    for (int i = 0; i < findNums.length; i++)
        findNums[i] = map.getOrDefault(findNums[i], -1);
    return findNums;
}