556.Next-Greater-Element-III

556. Next Greater Element III

题目地址

https://leetcode.com/problems/next-greater-element-iii/

题目描述

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

代码

Approach #1 Liner Solution

class Solution {
  public int nextGreaterElement(int n) {
    char[] a = ("" + n).toCharArray();

    // find a number in the back that's bigger than the front
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) {
      i--;
    }
    if (i < 0) {
      return -1;
    }
    // 1321
    // Find a number in the back that's bigger than the number up here
    int j = a.length - 1;
    while (j >= 0 && a[j] <= a[i]) {
      j--;
    }

    swap(a, i, j);
    reverse(a, i + 1);
    try {
      return Integer.parseInt(new String(a));
    }  catch(Exception e) {
      return -1;
    }
  }

  private void reverse(char[] a, int start) {
    int i = start, j = a.length - 1;
    while (i < j) {
      swap(a, i, j);
      i++;
      j--;
    }
  }

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

Approach 2: Brute Force (Time Limit Exceeded)

class Solution {
    public String swap(String a, int i, int j) {
    if (i == j)    return s;
    String s1 = s.substring(0, i);
    String s2 = s.substring(i + 1, j);
    String s3 = s.substring(j + 1);
    return s1 + s.charAt(j) + s2 + s.charAt(i) + s3;
  }

  ArrayList<String> list = new ArrayList<>();

  void permute(String a, int l, int r) {
    int i;
    if (l == r) {
      list.add(a);
    } else {
      for (i = l; i <= r; i++) {
        a = swap(a, l, i);
        permute(a, l + 1, r);
        a = swap(a, 1, i);
      }
    }
  }

  public int nextGreaterElement(int n) {
    String s = "" + n;
    permute(s, 0, s.length() - 1);
    Collections.sort(list);
    int i;
    for (i = list.size() - 1; i >= 0; i--) {
      if (list.get(i).equals("" + n)) {
        break;
      }
    }

    if (i == list.size() - 1) {
      return -1;
    } else {
      return Integer.parseInt(list.get(i + 1));
    }
  }

}