LeetCode题练习与总结：下一个更大元素 Ⅲ -- 556

一、题目描述

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

• 1 <= n <= 2^31 - 1

二、解题思路

1. 从右向左遍历数字n的每一位，找到第一个下降的数字，即找到第一个数字nums[i]，使得nums[i] < nums[i+1]。如果没有找到这样的数字，则说明n是一个递减序列，直接返回-1。

2. 从右向左再次遍历，找到第一个比nums[i]大的数字nums[j]，交换nums[i]和nums[j]。

3. 将nums[i+1]到nums[n-1]的数字进行升序排序，以确保得到的是大于n的最小数字。

4. 将数组转换成整数，检查是否超过32位整数的范围，如果没有，则返回该整数；否则返回-1。

三、具体代码

import java.util.Arrays;

class Solution {
    public int nextGreaterElement(int n) {
        char[] nums = String.valueOf(n).toCharArray();
        int i = nums.length - 2;
        
        // Step 1: Find the first decreasing element from the right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // If no such element is found, return -1
        if (i < 0) {
            return -1;
        }
        
        // Step 2: Find the first element greater than nums[i] from the right
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        
        // Swap nums[i] and nums[j]
        swap(nums, i, j);
        
        // Step 3: Reverse the sequence after i to get the smallest number
        reverse(nums, i + 1, nums.length - 1);
        
        // Step 4: Convert char array back to integer and check for 32-bit overflow
        long result = Long.parseLong(new String(nums));
        return (result <= Integer.MAX_VALUE) ? (int) result : -1;
    }
    
    private void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(char[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

这段代码定义了一个Solution类和一个nextGreaterElement方法，该方法实现了上述解题思路，并且包含了两个辅助方法swap和reverse用于交换字符数组的元素和反转数组的一部分。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 寻找第一个下降的数字：这个步骤需要从右向左遍历整个数组一次，时间复杂度为O(N)，其中N是数字n的位数。

• 寻找第一个比nums[i]大的数字：在最坏的情况下，可能需要再次遍历整个数组，时间复杂度为O(N)。

• 交换两个数字：这个操作的时间复杂度是O(1)。

• 反转数组的一部分：反转从i+1到nums.length - 1的部分，最坏情况下需要反转N/2个数字，时间复杂度为O(N)。

• 将字符数组转换成整数：这个操作的时间复杂度是O(N)，因为需要遍历整个数组。

综上所述，总的时间复杂度是O(N) + O(N) + O(1) + O(N) + O(N) = O(N)，其中N是数字n的位数。

2. 空间复杂度

• 字符数组nums：用于存储数字n的每一位，空间复杂度为O(N)。

• 辅助变量：如i, j, temp等，它们都是常数级别的空间，空间复杂度为O(1)。

• 方法调用栈：由于没有使用递归或额外的数据结构，方法调用栈的空间复杂度也是O(1)。

因此，总的空间复杂度是O(N) + O(1) = O(N)，其中N是数字n的位数。

五、总结知识点

• 数据类型转换：

  • 将整数n转换为字符数组nums，使用String.valueOf(n).toCharArray()。

• 字符数组操作：

  • 使用字符数组来表示数字，并对其进行操作，因为字符数组支持交换元素和反转操作。

• 循环和条件判断：

  • 使用while循环来遍历数组，寻找特定的元素位置。
  • 使用if语句来处理边界情况，如找不到下降元素时返回-1。

• 数组元素交换：

  • 定义了一个辅助方法swap来交换字符数组中的两个元素。

• 数组部分反转：

  • 定义了一个辅助方法reverse来反转字符数组的一部分，以便生成下一个更大的数字。

• 数学和逻辑：

  • 理解并实现找到下一个更大数字的逻辑，包括如何找到第一个下降的元素，以及如何找到第一个比它大的元素。

• 字符串和数字的相互转换：

  • 使用Long.parseLong(new String(nums))将字符数组转换回长整型数字。

• 溢出检查：

  • 在将字符数组转换回整数后，检查结果是否在32位整数的范围内，以避免溢出。

• 方法封装：

  • 将交换和反转操作封装为私有方法，以保持代码的整洁和可重用性。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。