Leetcode-556. Next Greater Element III 算法

前言：为了后续的实习面试，开始疯狂刷题，非常欢迎志同道合的朋友一起交流。因为时间比较紧张，目前的规划是先过一遍，写出能想到的最优算法，第二遍再考虑最优或者较优的方法。如有错误欢迎指正。博主首发CSDN，mcf171专栏。
博客链接：mcf171的博客

——————————————————————————————
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

这个题目其实可以理解成全排列的下一个。小心一个坑是，下一个排列必须在正整数范围内。

public class Solution { public int nextGreaterElement(int n) { String num = n + ""; char[] charArray = num.toCharArray(); if(num.length() < 2) return -1; int index = num.length() - 2; for(; index >= 0; index --){ if(num.charAt(index) < num.charAt(index + 1)) break; } if(index == -1) return -1; int swapIndex = index + 1; for(; swapIndex < num.length(); swapIndex ++){ if(num.charAt(swapIndex) <= num.charAt(index)) break; } swapIndex --; char temp = charArray[index]; charArray[index] = charArray[swapIndex]; charArray[swapIndex] = temp; Arrays.sort(charArray,index + 1, charArray.length); int result = 0; for(char ch : charArray) {result = result * 10 + (ch - '0'); if(result > Integer.MAX_VALUE / 10) return -1; }return result; } }

【Leetcode-556. Next Greater Element III】