LeetCode 556. Next Greater Element III

2021年09月15日 阅读数:5
这篇文章主要向大家介绍LeetCode 556. Next Greater Element III,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

原题连接在这里:https://leetcode.com/problems/next-greater-element-iii/description/html

题目:git

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 nand is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.post

Example 1:url

Input: 12
Output: 21

Example 2:spa

Input: 21
Output: -1

题解:code

若是每一位digit依次递减, 好比"54321"就没有next greater element. return -1.htm

因此说节点在于不是递减的位置, "52431", 找到 “2” 和 “4”的位置不是递减. 而后在2的后面比2大的最小digit, 这里是3.blog

"2", "3"换位, 变成"53421", 再把3后面的部分sort成从小到大 "53124"就是next greater element.ip

Time Complexity: O(x), x是n的digit 数目. 每一个digit不会走超过3遍.element

Space: O(x).

AC Java:

 1 class Solution {
 2     public int nextGreaterElement(int n) {
 3         char [] arr = (""+n).toCharArray();
 4         int i = arr.length-2;
 5         while(i>=0 && arr[i]>=arr[i+1]){
 6             i--;
 7         }
 8         
 9         if(i < 0){
10             return -1;
11         }
12         
13         int j = arr.length-1;
14         while(j>i && arr[j]<=arr[i]){
15             j--;
16         }
17         
18         swap(arr, i, j);
19         reverse(arr, i+1);
20         try{
21             return Integer.valueOf(new String(arr));
22         }catch(Exception e){
23             return -1;
24         }
25     }
26     
27     private void swap(char [] arr, int i, int j){
28         char temp = arr[i];
29         arr[i] = arr[j];
30         arr[j] = temp;
31     }
32     
33     private void reverse(char [] arr, int start){
34         int i = start;
35         int j = arr.length-1;
36         while(i < j){
37             swap(arr, i++, j--);
38         }
39     }
40 }

相似Next PermutationNext Greater Element INext Greater Element II.