给定一个数n如23121;给定一组数字a如[2 4 9]，求由a中元素组成的小于n的最大数

a: 1-9的不同数字

n：int32

分析

从n的高位到低位遍历假设当前位是bit，找寻arr满足条件的数分类讨论：

找到arr[i] == bit, 当前位置更新为bit，继续遍历低位
找到最大的arr[i] < bit，那么当前位置更新位arr[i], 后面所有位置全部更新为 max(arr)
min(arr) > bit, 当前位找不到比n更小，舍弃所有高位，低位全部选最大

经过上述的遍历筛选之后，能得到两个答案：

满足条件的最大。直接返回即可。
找到ans==n。继续分析ans==n，从低位遍历ans的每一位，从arr中找更小的一个值替换a. 找到值，替换，返回替换后的ansb. 所有值遍历完，找不到更小，所有位置都是min(ans) 那么返回0，表示找不到更小值

实现

Golang

func solve(n int, arr []int) int {
	// 将n从高位到低位用数组存储，方便按位置检索
	// 123 => []int{1,2,3}
	nArr := []int{}
	for n > 0 {
		// 加到数组前面
		nArr = append([]int{n % 10}, nArr...)
		n /= 10
	}
	// 将arr进行排序，方便找寻min，max 寻值可以用2分，更快，不过因为arr长度最大只有9[1-9], 所以也可以直接遍历
	sort.Ints(arr)
	// 按梳理条件分类讨论
	ans := 0
	// 从高位开始，定位n的位置
	pos := 0
	for pos < len(nArr) {
		bit := nArr[pos]
		pos++
		// 找到第一个>bit的索引idx, 那么arr[idx-1] <= bit
		idx := 0
		for idx < len(arr) && arr[idx] <= bit {
			idx++
		}
		if idx == 0 {
			// 当前找不到比bit更小的值，往前看有没有位置可以选更小元素
			// 1. 找到，那么该位置选择更小，后续位置全部最大
			// 2. 没有找到，前置全部是最小值，则舍弃最高位，后续位置全部选最大
			// pos当前在下一位，回到上一位，-2
			pos -= 2
			for pos >= 0 {
				cur := ans % 10
				ans /= 10
				if arr[0] == cur {
					pos--
					continue
				}
				// 存在更小值，找到更小值，替换
				idx := 0
				for arr[idx] < cur {
					idx++
				}
				ans = ans*10 + arr[idx-1]
				pos++
				break
			}
			// 如果没有找到，则去除最高位，此时ans=0
			if pos <= 0 {
				pos = 1
			}
			// 低位全部选择最大
			for pos < len(nArr) {
				ans = ans*10 + arr[len(arr)-1]
				pos++
			}
			return ans
		}
		// arr[idx-1] 是小于等于bit的最大值
		if arr[idx-1] < bit {
			ans = ans*10 + arr[idx-1]
			// 低位全部选择最大
			for pos < len(nArr) {
				ans = ans*10 + arr[len(arr)-1]
				pos++
			}
			return ans
		}
		// arr[idx-1] == bit
		ans = ans*10 + bit
		// 继续遍历低位
	}
	// 循环内没找到答案，此时ret=n 逆序遍历，找到更小的位置，替换
	pos = len(nArr) - 1
	for pos >= 0 {
		bit := nArr[pos]
		pos--
		idx := 0
		// 找到arr[idx]=bit， idx-1为要的元素
		for idx < len(arr) && arr[idx] < bit {
			idx++
		}
		// 找到了
		if idx > 0 {
			ans = ans*10 + bit
			for pos >= 0 {
				bit := nArr[pos]
				ans = ans*10 + bit
				pos--
			}
			// 因为是逆序遍历得到的答案，所以将ret逆序
			return reverse(ans)
		}
		// 没找到，继续遍历
		ans = ans*10 + bit
	}
	// 没找到
	return 0
}

func reverse(v int) int {
	ans := 0
	for v > 0 {
		ans = ans*10 + v%10
		v /= 10
	}
	return ans
}

验证：

示例1:
23121
[4,2,9]
22999

示例2:
19238479
[1,4,2,3,7]
17777777

示例3:
192482
1,5,3,2
155555

示例4:
333112342
4,5,6,7
77777777

示例5:
4441242
4,5,6
666666

示例6:
23121
2,3,4
22444