考點：單調棧
給定兩個沒有重復元素的數(shù)組 nums1 和 nums2 域帐，其中nums1 是 nums2 的子集。找到 nums1 中每個元素在 nums2 中的下一個比其大的值是整。
nums1 中數(shù)字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素肖揣。如果不存在，對應位置輸出-1浮入。
示例 1:
輸入: 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劲蜻。
注意:
nums1和nums2中所有元素是唯一的。
- 將num2倒序入棧
- 保持棧頂元素比新入棧元素大考余，否則出棧
- 結果暫存map中以提高返回處理速度
package main
import (
"container/list"
"fmt"
"strconv"
"strings"
)
func nextGreaterElement(nums1 []int, nums2 []int) []int {
var (
numList list.List
numMap = make(map[int] int, 10)
retList = nums1
)
for i := len(nums2) - 1; i >= 0; i -- {
var result int
if numList.Len() == 0 {
result = -1
}
for true {
if numList.Len() > 0 && numList.Back().Value.(int) <= nums2[i] {
numList.Remove(numList.Back())
} else {
break
}
}
if numList.Len() > 0 {
result = numList.Back().Value.(int)
} else {
result = -1
}
numList.PushBack(nums2[i])
numMap[nums2[i]] = result
}
for index, num := range nums1 {
retList[index] = numMap[num]
}
return retList
}
func main() {
var (
sum_list string
list_str []string
num_list1 = []int{}
num_list2 = []int{}
)
fmt.Println("輸入數(shù)組1:")
fmt.Scan(&sum_list)
list_str = strings.Split(sum_list, ",")
for _, str := range list_str {
tmp, _ := strconv.Atoi(str)
num_list1 = append(num_list1, tmp)
}
fmt.Println("輸入數(shù)組2:")
fmt.Scan(&sum_list)
list_str = strings.Split(sum_list, ",")
for _, str := range list_str {
tmp, _ := strconv.Atoi(str)
num_list2 = append(num_list2, tmp)
}
fmt.Println(nextGreaterElement(num_list1, num_list2))
}
