小于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;
}