給你兩個 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值。
nums1 中數(shù)字 x 的下一個更大元素是指 x 在 nums2 中對應(yīng)位置的右邊的第一個比 x 大的元素。如果不存在，對應(yīng)位置輸出 -1 。其中
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整數(shù) 互不相同
nums1 中的所有整數(shù)同樣出現(xiàn)在 nums2 中

例子

**輸入: **nums1 = [4,1,2], nums2 = [1,3,4,2].
**輸出: **[-1,3,-1]
解釋:
對于 num1 中的數(shù)字 4 ，你無法在第二個數(shù)組中找到下一個更大的數(shù)字，因此輸出 -1 。
對于 num1 中的數(shù)字 1 ，第二個數(shù)組中數(shù)字1右邊的下一個較大數(shù)字是 3 。
對于 num1 中的數(shù)字 2 ，第二個數(shù)組中沒有下一個更大的數(shù)字，因此輸出 -1 。
示例 2:

輸入: nums1 = [2,4], nums2 = [1,2,3,4].
**輸出: **[3,-1]
解釋:
對于 num1 中的數(shù)字 2 ，第二個數(shù)組中的下一個較大數(shù)字是 3 。
對于 num1 中的數(shù)字 4 ，第二個數(shù)組中沒有下一個更大的數(shù)字，因此輸出 -1 。

解題思路

1.哈希法

題意稍微解釋下, 其實(shí)就是依次遍歷數(shù)組1, 在數(shù)組2中找到數(shù)組1對應(yīng)元素后面最大的1個, 沒有返回-1

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

• 4, 在num2中4之后只有2, 2比4小, 返回-1
• 1, 在num2中1之后有3, 4, 2, 取第一個最大3, 返回3
• 2, 在num2中2之后無元素, 返回-1

返回結(jié)果 [-1, 3, -1]

因?yàn)閿?shù)組nums1和nums2沒有重復(fù)元素, 并且nums1是nums2的子集, 那么用哈希法處理此題是一個相對好理解方法

遍歷num2, 以每一項(xiàng)i做key, 以i之后第一個大于i的元素做value, 沒有則value為-1, 則有

代碼

未翻譯版

    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        
        var res = [Int](), dic = [Int:Int]()

        for i in 0..<nums2.count {
            for j in i+1..<nums2.count {
                if nums2[j] > nums2[i] {
                    dic[nums2[i]] = nums2[j]
                    break
                }
            }
            // 下面if 加不加都行
            //if dic.count < i + 1 {
            //    dic[nums2[i]] = -1
            //}
        }
        
        for i in 0..<nums1.count {
            res.append(dic[nums1[i]] ?? -1)
        }
            
        return res
    }

翻譯版

    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        
        // 定義結(jié)果res, 哈希表dic
        var res = [Int](), dic = [Int:Int]()

        // 遍歷nums2中每一個元素nums2[i]
        for i in 0..<nums2.count {

            // 遍歷i之后, 每一個元素
            for j in i+1..<nums2.count {

                // 找到后面第一個大于nums2[i]元素, 形成key-value
                if nums2[j] > nums2[i] {
                    dic[nums2[i]] = nums2[j]
                    break
                }
            }

            // 沒有value - 1, 下面if 加不加都行
            //if dic.count < i + 1 {
            //    dic[nums2[i]] = -1
            //}
        }
        
        // 遍歷num1, 依次添加數(shù)組
        for i in 0..<nums1.count {
            res.append(dic[nums1[i]] ?? -1)
        }
            
        return res
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址