貪心算法求解邊界最大數（拼多多2504、排列問題）

多多有兩個僅由正整數構成的數列 s1 和 s2，多多可以對 s1 進行任意次操作，每次操作可以置換 s1 中任意兩個數字的位置。多多想讓數列 s1 構成的數字盡可能大，但是不能比數列 s2 構成的數字大。請問在經過任意次操作后，滿足上述條件的數列 s1 構成的數字是多少。

s1 = 21453
s2 = 14682
輸出res = 14532

### 5.2 C++解決方案時間復雜度：
最壞情況：O(n!)
平均情況：O(n^2) 到 O(n^3)
最好情況：O(n)
空間復雜度：O(n)#include <algorithm>
#include <iostream>
#include <string>// 全局變量，用于存儲小于 s2 的 s1 的最大排列結果
std::string max_result = "";// 回溯函數，用于生成 s 的所有排列并找出符合條件的最大排列
void backtrack(std::string &s, int index, const std::string &s2) {// 當 index 等于 s 的長度時，說明已經生成了一個完整的排列if (index == s.length()) {// 檢查該排列是否小于 s2 且大于當前記錄的最大排列 max_resultif (s < s2 && s > max_result) {// 若滿足條件，則更新 max_resultmax_result = s;}return;}// 記錄當前位置可以使用的最大字符char max_char = s2[index];// 嘗試將 s 中 index 位置及其后面的每個位置的字符與 index 位置交換for (int i = index; i < s.length(); ++i) {// 剪枝 如果當前字符大于目標字符，跳過if (s[i] > max_char)continue;// 交換 s[index] 和 s[i] 的位置std::swap(s[index], s[i]);// 剪枝 如果當前前綴小于目標前綴，繼續遞歸if (s.substr(0, index + 1) <= s2.substr(0, index + 1)) {backtrack(s, index + 1, s2);}// 回溯操作，將字符交換回來std::swap(s[index], s[i]);//剪枝 如果已經找到了一個有效的排列，且當前字符等于目標字符，可以提前返回if (!max_result.empty() && s[i] == max_char) {break;}}
}// 主函數，用于找出小于 s2 的 s1 的最大排列
int largest_less_than(const std::string &s1, const std::string &s2) {// 檢查 s1 和 s2 的長度是否相等if (s1.length() > s2.length()) {return -1;}if(s1.length() < s2.length()){std::string s = s1;std::sort(s.begin(), s.end(), std::greater<char>());return stoi(s);}// 復制 s1 到 s 中，并對其進行降序排序std::string s = s1;std::sort(s.begin(), s.end(), std::greater<char>());// 調用回溯函數開始生成排列backtrack(s, 0, s2);// 返回結果return max_result.empty() ? -1 : std::stoi(max_result);
}int main() {// 定義示例字符串 s1std::string s1 = "67433";// 定義示例字符串 s2std::string s2 = "14682";// 調用 largest_less_than 函數得到結果int res = largest_less_than(s1, s2);// 輸出結果std::cout << "res = " << res << std::endl;return 0;
}