Leetcode Note: Go - Next Greater Element I

Add Binary - LeetCode
https://leetcode.com/problems/add-binary/

• Go 言語で取り組んだメモ

所感

• int 配列 nums1, nums2 を比較して Greater 要素となるか計算して int 配列を return する
  • greater は大きい
• 例: nums1 = [4,1,2], nums2 = [1,3,4,2]
  • 4: nums2 を走査していくと 4 があるが、次の greater element が無いため -1
  • 1: nums2 を走査していくと 1 があり、次の greater element は 3 なので 3
  • 2: nums2 を走査していくと 2 があるが、次の greater element が無いので -1
  • よって return [-1, 3, -1]

回答

Golang map solution - LeetCode Discuss
https://leetcode.com/problems/next-greater-element-i/discuss/736472/Golang-map-solution

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	res := make([]int, 0)
	m := make(map[int]int, 0)

	for i := 0; i < len(nums2); i++ {
		for j := i + 1; j < len(nums2); j++ {
			if nums2[i] < nums2[j] {
				m[nums2[i]] = nums2[j]
				break
			}
		}
		if m[nums2[i]] == 0 {
			m[nums2[i]] = -1
		}
	}

	for i := 0; i < len(nums1); i++ {
		res = append(res, m[nums1[i]])
	}

	return res
}

• nums2 の走査状況を map で管理
• loop for nums2
  • nums2[i] < nums2[j] であれば m[nums2[i]] = nums2[j] で map の value に num2[j] が記録される
    • これで nums2 の値と next greater element value が mapping される
  • nums2[i] < nums2[j] でなければ m[nums2[i]] = -1 で -1 が map の value に記録される
    • これで nums2 の値に対して next greater element が無いものには -1 が mapping される
• loop for nums1
  • nums1 の値で map の key を参照し、 value を return 用に append する