https://leetcode.com/problems/next-greater-element-i/

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

初始化一個map key=nums1值, value=nums1 index

初始化一個result = 全都-1，長度為 len(nums1)

初始化一個stack

for 走訪 nums2

• while (stack’s length > 0) & (current num > stack’s top)
  • top = stack.pop
  • if (stack’s top in map)
    • top’s index = map[top]
    • result[top’s index] = current
• stack.push(current)

return result

package main

import "fmt"

func main() {
	nums1, nums2 := []int{1, 3, 5, 2, 4}, []int{6, 5, 4, 3, 2, 1, 7}
	fmt.Println("RESULT:", nextGreaterElement(nums1, nums2))
}

func nextGreaterElement(nums1 []int, nums2 []int) []int {

	// init the map
	idxMap := map[int]int{}
	for i, num := range nums1 {
		idxMap[num] = i
	}

	// init the result array fill with -1
	result := make([]int, len(nums1))
	for i := range result {
		result[i] = -1
	}

	// init a stack
	stack := []int{}

	for _, num := range nums2 {

		for len(stack) > 0 && num > stack[len(stack)-1] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if topIdx, ok := idxMap[top]; ok {
				result[topIdx] = num
			}
		}

		stack = append(stack, num)
	}

	return result
}