2019-11-10
LeetCode 556. Next Greater Element III


impl Solution {
    fn next_permutation(nums: Vec<i32>) -> Option<Vec<i32>> {
        let mut nums = nums;
        let mut i = nums.len() - 1;
        while i > 0 {
            i -= 1;
            if nums[i] < nums[i + 1] {
                let mut j = nums.len() - 1;
                while nums[i] >= nums[j] {
                    j -= 1;
                }
                nums.swap(i, j);

                let mut low = i + 1;
                let mut high = nums.len() - 1;

                while low < high {
                    nums.swap(low, high);
                    low += 1;
                    high -= 1;
                }
                return Some(nums);
            }
        }
        None
    }
    pub fn next_greater_element(n: i32) -> i32 {
        let mut n = n;
        let mut digits = vec![];
        while n != 0 {
            digits.push(n % 10);

            n = n / 10;
        }
        digits.reverse();
        if let Some(greater) = Self::next_permutation(digits) {
            let mut res = 0_i32;
            for n in greater {
                let (shift_res, is_overflow) = res.overflowing_mul(10);
                if is_overflow {
                    return -1;
                }
                let (new_res, is_overflow) = shift_res.overflowing_add(n);
                if is_overflow {
                    return -1;
                }
                res = new_res;
            }
            return res
        }
        -1
    }
}