Question

556. Next Greater Element III

中文文档

Description

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:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

 

Constraints:

• 1 <= n <= 231 - 1

Solutions

Solution 1

class Solution:
  def nextGreaterElement(self, n: int) -> int:
    cs = list(str(n))
    n = len(cs)
    i, j = n - 2, n - 1
    while i >= 0 and cs[i] >= cs[i + 1]:
      i -= 1
    if i < 0:
      return -1
    while cs[i] >= cs[j]:
      j -= 1
    cs[i], cs[j] = cs[j], cs[i]
    cs[i + 1 :] = cs[i + 1 :][::-1]
    ans = int(''.join(cs))
    return -1 if ans > 2**31 - 1 else ans

class Solution {
  public int nextGreaterElement(int n) {
    char[] cs = String.valueOf(n).toCharArray();
    n = cs.length;
    int i = n - 2, j = n - 1;
    for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
      ;
    if (i < 0) {
      return -1;
    }
    for (; cs[i] >= cs[j]; --j)
      ;
    swap(cs, i, j);
    reverse(cs, i + 1, n - 1);
    long ans = Long.parseLong(String.valueOf(cs));
    return ans > Integer.MAX_VALUE ? -1 : (int) ans;
  }

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

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

class Solution {
public:
  int nextGreaterElement(int n) {
    string s = to_string(n);
    n = s.size();
    int i = n - 2, j = n - 1;
    for (; i >= 0 && s[i] >= s[i + 1]; --i)
      ;
    if (i < 0) return -1;
    for (; s[i] >= s[j]; --j)
      ;
    swap(s[i], s[j]);
    reverse(s.begin() + i + 1, s.end());
    long ans = stol(s);
    return ans > INT_MAX ? -1 : ans;
  }
};

func nextGreaterElement(n int) int {
  s := []byte(strconv.Itoa(n))
  n = len(s)
  i, j := n-2, n-1
  for ; i >= 0 && s[i] >= s[i+1]; i-- {
  }
  if i < 0 {
    return -1
  }
  for ; j >= 0 && s[i] >= s[j]; j-- {
  }
  s[i], s[j] = s[j], s[i]
  for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
    s[i], s[j] = s[j], s[i]
  }
  ans, _ := strconv.Atoi(string(s))
  if ans > math.MaxInt32 {
    return -1
  }
  return ans
}