LeetCode556-下一个更大元素III

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/next-greater-element-iii/

中文链接：https://leetcode-cn.com/problems/next-greater-element-iii/

题目详述

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1:

1
2
输入: 12
输出: 21

示例 2:

1
2
输入: 21
输出: -1

题目详解

  • 前两题 LeetCode496-下一个更大元素I、LeetCode503-下一个更大元素II 都是运用单调栈进行解答，本题与单调栈无关，实际上是求下一个排列。
  • 求下一个排列具有四个步骤。
  • 注意下一个排列不存在的情况和最终结果溢出的情况，这两种情况都应该返回 -1。
  • 为了避免对结果进行溢出判断，可以将结果转换为 long 型变量进行计算，最后判断是否超过 int 型变量的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class LeetCode_00556 {

    public int nextGreaterElement(int n) {
        if (n < 12) {
            return -1;
        }
        char[] cs = String.valueOf(n).toCharArray();
        // 1.从后往前找到第一组位置，满足 nums[i] < nums[i + 1]
        int i = cs.length - 2;
        while (i >= 0 && cs[i] >= cs[i + 1]) {
            --i;
        }
        // 不存在下一个排列
        if (i < 0) {
            return -1;
        }
        // 2.从后往前找到第一个位置，满足 nums[i] < nums[j]
        int j = cs.length - 1;
        while (cs[i] >= cs[j]) {
            --j;
        }
        // 3.交换 i、j 两处的值
        swap(cs, i, j);
        // 4.反转从位置 i + 1 开始到末尾的序列
        reverse(cs, i + 1, cs.length - 1);
//        int res = 0;
//        for (char c : cs) {
//            // 防溢出
//            int t = c - '0';
//            if (res > (Integer.MAX_VALUE - t) / 10) {
//                return -1;
//            }
//            res = res * 10 + t;
//        }
//        return res;
        long res = 0;
        for (char c : cs) {
            res = res * 10 + c - '0';
        }
        return res <= Integer.MAX_VALUE ? (int) res : -1;
    }

    private void reverse(char[] cs, int i, int j) {
        while (i < j) {
            swap(cs, i++, j--);
        }
    }

    private void swap(char[] cs, int i, int j) {
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;
    }
}