题目

• 给定一个数12445和一个数组[1,2,4]，可以重复使用，求能组成的 小于给定数 n 的最大整数

golang
package main

import (
	"fmt"
	"sort"
	"strconv"
)

func maxLessThan(n int, digits []int) int {
	sort.Ints(digits)

	s := []byte(strconv.Itoa(n))
	m := len(s)

	res := make([]byte, m)

	for i := 0; i < m; i++ {
		cur := int(s[i] - '0')

		// 找 <= cur 的最大数字
		idx := upperBound(digits, cur) - 1

		if idx >= 0 {
			res[i] = byte(digits[idx] + '0')

			// 当前位已经小于 n，后面全部填最大数
			if digits[idx] < cur {
				fillMax(res, i+1, digits[len(digits)-1])
				return toInt(res)
			}
		} else {
			// 当前位放不了，向前回退
			return backtrack(res, i, digits)
		}
	}

	// res == n，需要继续回退，保证严格小于 n
	return backtrack(res, m, digits)
}

func backtrack(res []byte, pos int, digits []int) int {
	for i := pos - 1; i >= 0; i-- {
		cur := int(res[i] - '0')

		idx := lowerBound(digits, cur) - 1
		if idx >= 0 {
			res[i] = byte(digits[idx] + '0')
			fillMax(res, i+1, digits[len(digits)-1])
			return toInt(res)
		}
	}

	// 无法组成同位数，只能少一位
	if len(res) == 1 {
		return -1
	}

	ans := 0
	for i := 0; i < len(res)-1; i++ {
		ans = ans*10 + digits[len(digits)-1]
	}
	return ans
}

func fillMax(res []byte, start int, maxDigit int) {
	for i := start; i < len(res); i++ {
		res[i] = byte(maxDigit + '0')
	}
}

func toInt(res []byte) int {
	ans, _ := strconv.Atoi(string(res))
	return ans
}

// 第一个 > target 的位置
func upperBound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := l + (r-l)/2
		if arr[mid] <= target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

// 第一个 >= target 的位置
func lowerBound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := l + (r-l)/2
		if arr[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func main() {
	fmt.Println(maxLessThan(2533, []int{2, 3, 5})) // 2525
	fmt.Println(maxLessThan(1000, []int{1, 2, 9})) // 999
	fmt.Println(maxLessThan(345, []int{3, 4, 5}))  // 344
	fmt.Println(maxLessThan(111, []int{1}))        // 11
	fmt.Println(maxLessThan(5, []int{7, 8}))       // -1
}