下一个更大元素 III
难度:
标签:
题目描述
代码结果
运行时间: 19 ms, 内存: 16.1 MB
/*
* Solution Idea:
* The approach will be similar, but we'll use Java Streams for some operations.
* Convert the integer to a list of characters, sort the suffix, and find the next permutation.
*/
import java.util.*;
public class NextGreaterElementStream {
public int nextGreaterElement(int n) {
List<Integer> digits = new ArrayList<>();
for (char c : String.valueOf(n).toCharArray()) {
digits.add(c - '0');
}
int i = digits.size() - 2;
// Step 2: Find the first decreasing element
while (i >= 0 && digits.get(i) >= digits.get(i + 1)) {
i--;
}
if (i == -1) {
return -1;
}
int j = digits.size() - 1;
// Step 3: Find the next bigger element
while (digits.get(j) <= digits.get(i)) {
j--;
}
Collections.swap(digits, i, j);
// Step 4: Reverse the sublist
Collections.reverse(digits.subList(i + 1, digits.size()));
// Convert to a number
long result = digits.stream().mapToLong(x -> x).reduce(0, (a, b) -> 10 * a + b);
return (result <= Integer.MAX_VALUE) ? (int) result : -1;
}
}解释
方法:
该题解的思路是：首先将整数 n 的每一位数字存入数组 digits 中。然后从数组末尾开始向前遍历，找到第一个满足 digits[i] < digits[i+1] 的位置 idx。如果找不到这样的位置，说明整数 n 已经是最大的排列，直接返回 -1。否则，再从数组末尾开始向前遍历，找到第一个满足 digits[i] > digits[idx] 的位置 i，交换 digits[idx] 和 digits[i]，然后将 digits[idx+1:] 部分翻转。最后，将数组 digits 转换成整数 ans，并检查是否超出了 32 位整数的范围。如果超出范围，返回 -1，否则返回 ans。
时间复杂度:
O(log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
在寻找 idx 的过程中，为什么选择寻找第一个 digits[i] < digits[i+1] 的位置并将其作为交换的起点？
▷🦆
执行 digits[idx] 和 digits[i] 交换后，为什么需要将 digits[idx+1:] 部分进行翻转？
▷🦆
数组 digits 翻转操作是否可以通过其他方式实现，有什么不同的效果？
▷🦆
当转换数组 digits 为整数 ans 时，你是如何确保不超出 32 位整数的范围的？特别是在进行 ans = ans * 10 + d 这一步时。
▷相关问题
下一个更大元素 I
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109