- 正确答案：该问题本质是“下一个更小的字典序排列”（Next Smaller Permutation）问题，即在由给定数字（允许重复）组成的、不包含前导零的所有合法整数中，找出严格小于N的最大整数。若不存在，则返回空或-1。核心解法是：从右向左找第一个“可下降位置”，再在其右侧找最大的但小于它的数字进行交换，最后将右侧子序列按**降序排列**（而非升序！这是与“下一个更大排列”的关键区别）以保证结果最大且仍小于原数。 - 解答思路： 1. 将N转换为字符数组（或数字数组）digits，便于逐位操作； 2. 从右向左扫描，找到第一个下标i，使得存在j > i，满足digits[j] < digits[i] —— 即右侧存在比当前位更小的数字，才可能通过调整得到更小数；实际高效做法是：从右向左找第一个“非递增断点”：即找最大i，使得digits[i] > digits[i+1]（因为右侧若为单调不降，则无法通过i位变小而获得更小整体值；只有当i位比右边某位大时，才可将i位换为右侧中小于它的最大者）； 3. 在i+1到末尾的子数组中，从右向左找第一个k，使得digits[k] < digits[i]（因右侧子数组是单调不降的，故最右一个满足条件的即为最大可行候选）； 4. 交换digits[i]与digits[k]； 5. 将i+1到末尾的子数组**反转（即变为严格降序）** —— 注意：此处不是升序！因为我们要在交换后使右侧尽可能大（从而整体数最大），但又必须小于原数。由于已固定前i+1位（其中第i位已变小），右侧应取所有剩余数字能构成的最大排列，即降序排列； 6. 检查结果是否含前导零：若首位为'0'且长度>1，则该排列非法（不是有效整数），需回溯处理或跳过——但注意：题目限定“用给定数字排列组合”，隐含输入数字集合即N的各位数字（multiset），因此我们只能重排N的各位，不能增删。故若N本身无前导零，则结果首位为0即非法，此时需继续寻找更早的可交换位置，或判定无解； 7. 特殊情况处理：若整个数组单调不降（如"1234"），则不存在更小排列，返回-1。 - 深度知识讲解：本题是LeetCode 1053. Previous Permutation With One Swap（简化版）与经典“next permutation”问题的逆向变种，考察对字典序排列生成原理的深刻理解。底层依赖两个关键性质：（1）字典序比较本质是高位优先：因此修改越靠右的位置，对数值影响越小，有利于保留高位不变而微调低位；（2）对于固定前缀，后续数字的**最大可能排列是降序排列**，最小是升序排列——这正是为何“下一个更大排列”中交换后要升序（取最小可能后续），而“上一个更小排列”中交换后要降序（取最大可能后续）。数据结构层面，无需额外空间，原地算法O(1)空间；时间O(d)，d为位数。关键在于理解单调性与贪心策略的结合：第一步找i是贪心定位“最右可优化位”，第二步找k是贪心选“右侧最大可行替代”，第三步降序是贪心构造“后续最大值”。进阶考点延伸： - 若题目允许使用给定数字集合（非N的各位，而是单独给一个数字数组，如[1,3,5,7]），则需先生成所有不重复排列（考虑去重），再过滤< N的最大值——此时复杂度指数级，需剪枝DFS或利用数位DP； - 若数字可重复使用（如每位可任选给定集合中的数字），则转为数位DP问题：dp[pos][tight][started]，状态记录当前位置、是否受N上限限制、是否已开始填数（避免前导零）； - 底层实现中，判断单调性时需注意：右侧子数组在步骤2后是“非递减”的（即升序或平序），这是由反向扫描第一个i满足digits[i] > digits[i+1]所保证的（因为若i+1到end是升序，则i位是首个破坏升序的位置）；因此步骤3中从右往左找第一个 digits[i+1] i = n - 2 while i >= 0 and digits[i] <= digits[i+1]: i -= 1 if i < 0: return -1 // no smaller permutation exists // Step 2: find largest j > i such that digits[j] < digits[i] j = n - 1 while digits[j] >= digits[i]: j -= 1 // Step 3: swap swap(digits[i], digits[j]) // Step 4: reverse suffix starting at i+1 to make it descending (maximizes suffix) reverse(digits[i+1:]) // Step 5: check leading zero if digits[0] == '0' and n > 1: return -1 // invalid number return int(''.join(digits)) - 补充说明与边界案例：例1：N = 321 → digits=[3,2,1] i=0（因3>2），j=2（因1<3），swap→[1,2,3]，reverse suffix [2,3]→[3,2] → [1,3,2]？错误！注意：swap后是[1,2,3]，suffix是索引1~2即[2,3]，reverse得[3,2]，最终[1,3,2]=132，但正确答案应为312？不对——重新模拟：初始[3,2,1]，i=0（3>2成立）；j从右找第一个<3的：j=2（1<3），swap[0]和[2]→[1,2,3]；suffix=[2,3]，reverse→[3,2]，得[1,3,2]=132。但321的更小排列有312、231、213、132、123，其中最大<321的是312。说明上述逻辑有误！修正关键：上述伪代码描述的是“标准上一个字典序排列”，但标准算法中，步骤2的右侧子数组是升序的，因此找j应是找**小于digits[i]的最大值**，而升序数组中该值位于最右满足条件处——但[3,2,1]的右侧子数组i+1~end是[2,1]，它并非升序！所以原始扫描条件错误。正确定义：标准算法中，“下一个更大排列”的前置条件是右侧为非递增（即降序），而“上一个更小排列”要求右侧为非递减（升序）。但在[3,2,1]中，从右看是降序，因此i应为第一个使右侧非降序被破坏的位置。正确做法是：对于prevPermutation：从右向左找第一个i，使得存在j>i且digits[j] min(digits[i+1:])，但高效做法是：先确保右侧是升序——所以应从右向左找第一个i，使得digits[i] > digits[i+1] 不成立？不。实际标准算法（C++ std::prev_permutation）逻辑： 1. 从后往前找第一个相邻升序对的左边元素：即找最大i，使得digits[i] > digits[i+1] —— 这保证了i+1到end是升序（非降序）； 2. 然后在i+1到end中，从后往前找第一个j，使得digits[j] < digits[i]（因升序，此j即为小于digits[i]的最大值）； 3. swap(i,j)； 4. reverse(i+1, end) —— 注意：reverse后i+1到end变为降序，即最大排列。验证[3,2,1]： i: 检查i=1: digits[1]=2, digits[2]=1 → 2>1，成立；i=0: digits[0]=3, digits[1]=2 → 3>2，成立；取最大i，即i=1？但标准算法取的是**最大i满足digits[i] > digits[i+1]**，所以i=1（因i=1满足，i=0也满足，最大是i=0？不，i=0和i=1都满足，最大i是0？索引0是最高位）。正确遍历：i从n-2 downto 0： i=1: digits[1]=2, digits[2]=1 → 2>1 → 找到，break，i=1。然后在[2]（即索引2）中找j：digits[2]=1 < digits[1]=2 → j=2。 swap digits[1]和digits[2] → [3,1,2] reverse suffix from i+1=2 → suffix is [2] → unchanged → [3,1,2] = 312 ✓ 所以步骤1应为：从右向左找**最大i**（即最靠右）使得digits[i] > digits[i+1] —— 这是为了让改动位置尽量靠右，从而保留高位不变。因此循环应为： i = n - 2 while i >= 0 and digits[i] <= digits[i+1]: i -= 1 if i < 0: return -1 对[3,2,1]： i=1: digits[1]=2 <= digits[2]=1? No, 2>1 → condition fails, so break with i=1. 对[1,2,3]：i=1: 2<=3 → continue; i=0: 1<=2 → continue; i=-1 → return -1. 对[1,3,2]：i=1: 3>2 → break, i=1; j: from end, first <3 is 2 at j=2; swap→[1,2,3]; reverse suffix [3]→[3] → [1,2,3]，但123<132，正确。因此最终修正伪代码： digits = list(str(N)) n = len(digits) i = n - 2 while i >= 0 and digits[i] <= digits[i+1]: i -= 1 if i < 0: return -1 j = n - 1 while digits[j] >= digits[i]: j -= 1 swap(digits[i], digits[j]) // reverse the suffix starting at i+1 left, right = i + 1, n - 1 while left < right: swap(digits[left], digits[right]) left += 1 right -= 1 if digits[0] == '0' and n > 1: return -1 return int(''.join(digits))

字节测开实习一面

全站热榜

创作者周榜