Formatted question description: https://leetcode.ca/all/556.html

556. Next Greater Element III (Medium)

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

Example 1:

Input: 12
Output: 21

 

Example 2:

Input: 21
Output: -1

 

Related Topics:
String

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/next-greater-element-iii/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int nextGreaterElement(int n) {
        auto s = to_string(n);
        for (int i = s.size() - 2; i >= 0; --i) {
            if (s[i] >= s[i + 1]) continue;
            int j = lower_bound(s.begin() + i + 1, s.end(), s[i], greater<int>()) - s.begin() - 1;
            swap(s[i], s[j]);
            sort(s.begin() + i + 1, s.end());
            long n = stol(s);
            return n > INT_MAX ? -1 : n;
        }
        return -1;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/next-greater-element-iii
// Time: O(1)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/85740/c-4-lines-next_permutation
class Solution {
public:
    int nextGreaterElement(int n) {
      auto digits = to_string(n);
      next_permutation(begin(digits), end(digits));
      auto ans = stol(digits);
      return (ans > INT_MAX || ans <= n) ? -1 : ans;
    }
};

Java

  • class Solution {
        public int nextGreaterElement(int n) {
            char[] array = String.valueOf(n).toCharArray();
            boolean next = nextPermutation(array);
            if (!next)
                return -1;
            String nextGreaterElementStr = new String(array);
            long nextGreaterElementLong = Long.parseLong(nextGreaterElementStr);
            if (nextGreaterElementLong > Integer.MAX_VALUE)
                return -1;
            else {
                int nextGreaterElement = (int) nextGreaterElementLong;
                return nextGreaterElement;
            }
        }
    
        public boolean nextPermutation(char[] array) {
            int length = array.length;
            int index = -1;
            char curChar = Character.MAX_VALUE;
            for (int i = length - 1; i > 0; i--) {
                int difference = array[i] - array[i - 1];
                if (difference > 0) {
                    index = i - 1;
                    curChar = array[i - 1];
                    break;
                }
            }
            if (index < 0) {
                Arrays.sort(array);
                return false;
            }
            int nextIndex = -1;
            char nextChar = Character.MAX_VALUE;
            for (int i = index + 1; i < length; i++) {
                if (array[i] > curChar && array[i] < nextChar) {
                    nextIndex = i;
                    nextChar = array[i];
                }
            }
            array[index] = nextChar;
            array[nextIndex] = curChar;
            Arrays.sort(array, index + 1, length);
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/next-greater-element-iii/
    // Time: O(1)
    // Space: O(1)
    class Solution {
    public:
        int nextGreaterElement(int n) {
            auto s = to_string(n);
            for (int i = s.size() - 2; i >= 0; --i) {
                if (s[i] >= s[i + 1]) continue;
                int j = lower_bound(s.begin() + i + 1, s.end(), s[i], greater<int>()) - s.begin() - 1;
                swap(s[i], s[j]);
                sort(s.begin() + i + 1, s.end());
                long n = stol(s);
                return n > INT_MAX ? -1 : n;
            }
            return -1;
        }
    };
    
  • class Solution(object):
      def nextGreaterElement(self, n):
        """
        :type n: int
        :rtype: int
        """
        num = n
        n = list(str(n))
        pos = leftMost = len(n) - 1
        for i in reversed(range(0, len(n) - 1)):
          if n[i] < n[i + 1]:
            leftMost = i
            break
        for i in reversed(range(leftMost + 1, len(n))):
          if n[i] > n[leftMost]:
            pos = i
            break
    
        n[leftMost], n[pos] = n[pos], n[leftMost]
        n[leftMost + 1:] = sorted(n[leftMost + 1:])
        n = int("".join(n))
        print
        n
        if n <= num or n > 0x7fffffff:
          return -1
        return n
    
    

All Problems

All Solutions