题目

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:

  1. Input: n = 12
  2. Output: 21

Example 2:

  1. Input: n = 21
  2. Output: -1

Constraints:

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

题意

给定一个数n，用n中所有位上的数字拼出另一个数m，使m恰好是大于n的最小的整数。

思路

可以看做是31. Next Permutation问题的变体，直接把n拆成单位数组成的数字，用next permutation的方法求值，注意溢出处理即可。

代码实现

Java

  1. class Solution {
  2.     public int nextGreaterElement(int n) {
  3.         int ans = 0;
  4.         char[] digits = (n + "").toCharArray();
  6.         int p = digits.length - 1;
  7.         while (p >= 1 && digits[p] <= digits[p - 1]) {
  8.             p--;
  9.         }
  10.         if (p == 0) return -1;
  12.         int q = p - 1;
  13.         p = digits.length - 1;
  14.         while (digits[p] <= digits[q]) {
  15.             p--;
  16.         }
  18.         swap(digits, p, q);
  19.         reverse(digits, q + 1, digits.length - 1);
  21.         for (int i = 0; i < digits.length; i++) {
  22.             int d = digits[i] - '0';
  23.               // 防止溢出
  24.             if (ans > Integer.MAX_VALUE / 10 || ans == Integer.MAX_VALUE / 10 && d > 7) {
  25.                 return -1;
  26.             }
  27.             ans = ans * 10 + d;
  28.         }
  30.         return ans;
  31.     }
  33.     private void swap(char[] A, int i, int j) {
  34.         char tmp = A[i];
  35.         A[i] = A[j];
  36.         A[j] = tmp;
  37.     }
  39.     private void reverse(char[] A, int p, int q) {
  40.         while (p < q) {
  41.             swap(A, p++, q--);
  42.         }
  43.     }
  44. }