【问题描述】
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
【示例1】
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
【示例2】
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2，第二个数组中的下一个较大数字是3。
对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
【提示】
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
【思路1】第一种想法很容易就能想到
1、遍历num1 num2，找到num1中等于num2中的元素的下标index
2、从index+1遍历到num2.count
3、找到比当前值大的值返回，没有找到返回-1
4、时间复杂度O(n^2)
5、空间复杂度O(n)
代码实现：
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var reslut = [Int]()
for n in nums1 {
var tmp = -1
var indexTmp = 0
for (index,nn) in nums2.enumerated() {
if n == nn {
indexTmp = index
}
}
if indexTmp+1 < nums2.count {
for i in indexTmp+1..<nums2.count {
if nums2[i] > n {
tmp = nums2[i]
break
}
}
}
reslut.append(tmp)
}
return reslut
}
【思路2】
1、使用单调栈，单调栈：单调栈是一种特殊的栈，特殊之处在于栈内元素都保持单调性，有单调递增和单调递减
2、单调栈可以解决 下一个更大元素 之类的问题
3、数组nums1是nums2的子集，所以把数组nums2中的每个数字右边大于当前元素的值求出即可
4、倒序插入到栈中
5、使用map[int:int]来存储每个元素所对应的下一个大于它的值或者-1
6、时间复杂度O(n)
7、空间复杂度O(n)
代码实现
栈-数据结构
struct Stack {
fileprivate var arr = [Int]()
mutating func pop() -> Int {
return self.arr.removeLast()
}
mutating func push(_ num:Int) {
self.arr.append(num)
}
func isEmpty() -> Bool {
return self.arr.isEmpty
}
func peek() -> Int? {
return self.arr.last
}
}
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var reslut = [Int]()
var stack = Stack.init()
var map = [Int:Int]()
for i in (0..<nums2.count).reversed() { //倒序插入,从数组后边开始
var tmp = -1
while !stack.isEmpty() && stack.peek()! < nums2[i] { //如果栈内当前小于num，栈pop
stack.pop()
}
if !stack.isEmpty() && stack.peek()! > nums2[i] {//如果栈内的元素大于当前指向的元素，赋值tmp
tmp = stack.peek()!
}
stack.push(nums2[i])
map[nums2[i]] = tmp
}
for n in nums1 {
reslut.append(map[n] ?? 0)
}
return reslut
}
