小于n的最大数 - 贪心算法 - C++

字节经典面试题
给定一个整数n，并从1~9中给定若干个可以使用的数字，根据上述两个条件，得到每一位都为给定可使用数字的、最大的小于整数n的数，例如，给定可以使用的数字为 {2,3,8} 三个数：给定 n=3589，输出3388；给定 n=8234，输出8233；……

#include <iostream>
#include <ostream>
#include <vector>
#include <algorithm>
using namespace std;
//找到小于x的最大值
int find_x(const vector<int>& digits, int x) {
    for (auto it = digits.rbegin(); it < digits.rend(); it++) {
        if (*it < x) {   
            return *it;
        }
    }
    return 0;
}
int process(vector<int>& digits, int n){
	
	sort(digits.begin(), digits.end());
	vector<int> aim;
	while(n>0){
		aim.push_back(n%10);
		n/=10;
        //cout<<n<<endl;
	}
	vector<int>ans(aim.size(), 0);
	for(int i=aim.size()-1; i>=0; i--){
		int now = find_x(digits, aim[i]);
		
		//当前的第i位找不到不合适，回溯降级需要降级
		if(now==0 && i==0){
			while(i<aim.size() && now==0){
				now = find_x(digits, aim[i]);
				i++;
			}
			//找到最高位还没有找到合适的，就要降级了
			if(i==aim.size()){
				ans = vector<int>(aim.size()-1, *(digits.end()-1));
				break;
			}else{
				//找到合适的了
				ans[i] = now;
				for(int k=0;k<i;k++){
					//后面的位都补充最大的数
					ans[k]=*digits.end();
				}
				break;
			}
		}else if(now ==0 ){
            now = digits[0];
        }
		ans[i]=now;
	}
	
	int ret=0;
	for(int m=ans.size()-1; m>=0; m--){
		ret*=10;
		ret+=ans[m];
	}
	return ret;
}

int main()
{
	vector<int> m_digits= { 2,8,3 };
   cout <<process(m_digits, 2222) <<endl;
   return 0;
}