556. Next Greater Element III

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public string Swap(string s, int i0, int i1) {
        if (i0 == i1) return s;
        var chars = s.ToCharArray();
        var temp = chars[i0];
        chars[i0] = chars[i1];
        chars[i1] = temp;
        return new string(chars);
    }
    private List<string> list = new List<string>();
    private void Permute(string a, int l, int r) {
        if (l == r) {
            list.Add(a);
        } else {
            for (int i = l; i <= r; i++) {
                a = Swap(a, l, i);
                Permute(a, l + 1, r);
                a = Swap(a, l, i);
            }
        }
    }
    public int NextGreaterElement(int n) {
        string s = n.ToString();
        Permute(s, 0, s.Length - 1);
        list.Sort();
        int index = list.IndexOf(s);
        if (index != -1 && index < list.Count - 1) {
            int result = int.Parse(list[index + 1]);
            if (result <= int.MaxValue) return result;
        }
        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string Swap(string s, int i0, int i1) {
        if (i0 == i1) return s;
        var chars = s.ToCharArray();
        var temp = chars[i0];
        chars[i0] = chars[i1];
        chars[i1] = temp;
        return new string(chars);
    }
    private List<string> list = new List<string>();
    private void Permute(string a, int l, int r) {
        if (l == r) {
            list.push_back(a);
        } else {
            for (int i = l; i <= r; i++) {
                a = Swap(a, l, i);
                Permute(a, l + 1, r);
                a = Swap(a, l, i);
            }
        }
    }
    public int NextGreaterElement(int n) {
        string s = n.ToString();
        Permute(s, 0, s.size() - 1);
        list.Sort();
        int index = list.IndexOf(s);
        if (index != -1 && index < list.size() - 1) {
            int result = int.Parse(list[index + 1]);
            if (result <= int.MaxValue) return result;
        }
        return -1;
    }
}

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public String swap(String s, int i0, int i1) {
        if (i0 == i1)
            return s;
        String s1 = s.substring(0, i0);
        String s2 = s.substring(i0 + 1, i1);
        String s3 = s.substring(i1 + 1);
        return s1 + s.charAt(i1) + s2 + s.charAt(i0) + 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, l, 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;
        }
        return i == list.size() - 1 ? -1 : Integer.parseInt(list.get(i + 1));
    }
}

class Solution {
    swap(s, i0, i1) {
        if (i0 === i1) return s;
        let chars = s.split('');
        [chars[i0], chars[i1]] = [chars[i1], chars[i0]];
        return chars.join('');
    }

    constructor() {
        this.list = [];
    }

    permute(a, l, r) {
        if (l === r) {
            this.list.push(a);
        } else {
            for (let i = l; i <= r; i++) {
                a = this.swap(a, l, i);
                this.permute(a, l + 1, r);
                a = this.swap(a, l, i);
            }
        }
    }

    nextGreaterElement(n) {
        let s = '' + n;
        this.permute(s, 0, s.length - 1);
        this.list.sort();
        let index = this.list.indexOf(s);
        if (index !== -1 && index < this.list.length - 1) {
            let result = parseInt(this.list[index + 1]);
            if (result <= 2147483647) {
                return result;
            }
        }
        return -1;
    }
}

class Solution:
    def swap(self, s, i0, i1):
        if i0 == i1:
            return s
        s = list(s)
        s[i0], s[i1] = s[i1], s[i0]
        return ''.join(s)
    
    def permute(self, a, l, r):
        if l == r:
            self.list.append(a)
        else:
            for i in range(l, r + 1):
                a = self.swap(a, l, i)
                self.permute(a, l + 1, r)
                a = self.swap(a, l, i)
    
    def nextGreaterElement(self, n: int) -> int:
        s = str(n)
        self.list = []
        self.permute(s, 0, len(s) - 1)
        self.list.sort()
        if s in self.list:
            index = self.list.index(s)
            if index < len(self.list) - 1:
                result = int(self.list[index + 1])
                if result <= 2**31 - 1:
                    return result
        return -1

package main

import (
    "fmt"
    "sort"
    "strconv"
)

func swap(s string, i0, i1 int) string {
    if i0 == i1 {
        return s
    }
    runes := []rune(s)
    runes[i0], runes[i1] = runes[i1], runes[i0]
    return string(runes)
}

var list []string

func permute(a string, l, r int) {
    if l == r {
        list = append(list, a)
    } else {
        for i := l; i <= r; i++ {
            a = swap(a, l, i)
            permute(a, l+1, r)
            a = swap(a, l, i)
        }
    }
}

func nextGreaterElement(n int) int {
    s := strconv.Itoa(n)
    list = []string{}
    permute(s, 0, len(s)-1)
    sort.Strings(list)
    for i := range list {
        if list[i] == s {
            if i < len(list)-1 {
                result, _ := strconv.Atoi(list[i+1])
                if result <= 2147483647 {
                    return result
                }
            }
        }
    }
    return -1
}

func main() {
    n := 12345
    fmt.Println(nextGreaterElement(n)) // Output: 12354
}

Explanation

Algorithm

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12

Output: 21

👨‍💻

Алгоритм:

Нахождение и перестановка цифр

Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

Обратный порядок оставшихся цифр

Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

Проверка результата и преобразование обратно в число

Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎