给定一个正整数n，请将n中的每位数字重新排列并组成一个新数， 要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。 例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、 132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231； 例2：n=123，123中每位上的数字依次是1、2、3，重新排列组成的新数有312、321、231、 213、132，新数中不存在小于123的正整数，故输出-1。 输入 输入一个正整数 𝑛 ( 1 ≤ 𝑛 < 2 63 ) 输出 输出一个正整数，表示符合要求的最大正整数 样例输入 复制 312 样例输出 复制 231

```cpp #include <iostream> #include <string> #include <algorithm> #include <climits> using namespace std; long long findMaxSmallerNumber(long long n) { string s = to_string(n); int len = s.length(); long long result = -1; // 从右向左找到第一个可以交换的位置 for (int i = len - 2; i >= 0; i--) { // 在i的右侧找到比s[i]小的最大数字 char maxSmaller = '0' - 1; int maxIndex = -1; for (int j = i + 1; j < len; j++) { if (s[j] < s[i] && s[j] > maxSmaller) { maxSmaller = s[j]; maxIndex = j; } } // 如果找到了可以交换的数字 if (maxIndex != -1) { // 交换这两个数字 swap(s[i], s[maxIndex]); // 将i位置之后的数字按降序排列 sort(s.begin() + i + 1, s.end(), greater<char>()); // 转换为数字并检查是否小于n long long candidate = stoll(s); if (candidate < n) { result = candidate; break; } // 恢复原始字符串继续搜索 s = to_string(n); } } return result; } int main() { long long n; cin >> n; cout << findMaxSmallerNumber(n) << endl; return 0; } ``` 代码说明： 1. 算法思路： - 将数字转换为字符串便于处理 - 从右向左找到第一个可以交换的位置（当前位置的数字大于右侧某个数字） - 在当前位置右侧找到比当前数字小的最大数字进行交换 - 交换后，将当前位置之后的数字按降序排列，确保得到的是小于原数的最大数 2. 关键步骤： - 使用`to_string()`将数字转为字符串 - 双重循环查找可交换的位置 - 使用`swap()`进行字符交换 - 使用`sort()`配合`greater<char>()`进行降序排列 - 使用`stoll()`将字符串转回长整型 3. 边界情况： - 输入为个位数时，直接返回-1 - 数字已经是最小排列时，返回-1 - 处理大数时使用`long long`类型 4. 时间复杂度：O(n²)，其中n是数字的位数 5. 空间复杂度：O(n)，用于存储字符串 示例验证： - 输入：312 → 输出：231 - 输入：123 → 输出：-1 - 输入：21 → 输出：12 - 输入：1 → 输出：-1 [2026-01-11 13:31:00 | AI问答 | 643点数解答]