leetcode-go/hard/321.create-maximum-number.go

func maxNumber(nums1 []int, nums2 []int, k int) []int {
	m, n := len(nums1), len(nums2)
	max := make([]int, m+n)
	for i := maxInt(0, k-n); i <= minInt(k, m); i++ {
		num := merge(pick(nums1, i), pick(nums2, k-i))
		if less(max, num) {
			max = num
		}
	}
	return max
}

func less(nums1, nums2 []int) bool {
	for i := range nums1 {
		if nums1[i] < nums2[i] {
			return true
		} else if nums2[i] < nums1[i] {
			return false
		}
	}
	return false
}

func pick(nums []int, k int) []int {
	n := len(nums)
	st := make([]int, 0)
loop:
	for i := 0; i < n; i++ {
		for {
			if l := len(st); l+n-i == k {
				st = append(st, nums[i:]...)
				break loop
			} else if 0 < l && st[l-1] < nums[i] {
				st = st[:l-1]
			} else {
				st = append(st, nums[i])
				break
			}
		}
	}
	return st[:k]
}

func merge(nums1, nums2 []int) []int {
	m, n := len(nums1), len(nums2)
	res := make([]int, m+n)
	i, i1, i2 := 0, 0, 0
	for mv1 := false; i1 < m && i2 < n; i++ {
		if nums1[i1] < nums2[i2] {
			mv1 = false
		} else if nums2[i2] < nums1[i1] {
			mv1 = true
		} else {
			for j1, j2, n1, n2 := i1+1, i2+1, 0, 0; (j1 < m || j2 < n) && n1 == n2; j1, j2 = j1+1, j2+1 {
				if m <= j1 {
					n1 = 0
				} else {
					n1 = nums1[j1]
				}
				if n <= j2 {
					n2 = 0
				} else {
					n2 = nums2[j2]
				}
				if n1 < n2 {
					mv1 = false
				} else if n2 < n1 {
					mv1 = true
				}
			}
		}
		if mv1 {
			res[i] = nums1[i1]
			i1++
		} else {
			res[i] = nums2[i2]
			i2++
		}
	}
	if i1 != m {
		copy(res[i:], nums1[i1:])
	}
	if i2 != n {
		copy(res[i:], nums2[i2:])
	}
	return res
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}