【LeetCode】556. 下一个更大元素 III

ゞ浴缸里的玫瑰 2022-05-08 09:40 168阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/next-greater-element-iii/description/][https_leetcode-cn.com_problems_next-greater-element-iii_description]

#### 题目描述 ####

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

#### 示例 ####

输入: 12  
输出: 21

输入: 21  
输出: -1

#### 解决方法 ####

将n中每一位取出存入vector容器中，即可转化成第31题求下一个排列的问题

class Solution { 
    public:
        int nextGreaterElement(int n) { 
            // 将n中每一位取出，转化成31. 下一个排列的题
            
            //第一步，将n每一位取出存入vector
            vector<int> nums;
            while(n){ 
                nums.push_back(n%10);
                n/=10;
            }
            reverse(nums.begin(),nums.end());
            
            //第二步，求下一个排列
            int pos=-1;
            for (int i=nums.size()-1;i>=1;i--){ 
                if (nums[i]>nums[i-1]){ 
                    pos=i-1;
                    break;
                }
            }
            if (pos!=-1){  //若pos==-1，则这是一个降序序列，表示不存在下一个更大元素
                for (int i=nums.size()-1;i>=pos+1;i--){  
                    if (nums[i]>nums[pos]){ 
                        swap(nums[i],nums[pos]);
                        break;
                    }
                }
                reverse(nums.begin()+pos+1,nums.end()); 
            }
            else return -1;
            
            //第三步，从vector取出每一位转化成int型
            long int result=0;
            for (int i=0;i<nums.size();i++) result=result*10+nums[i];
            if (result>INT_MAX) return -1;
            return result;
        }
    };

[https_leetcode-cn.com_problems_next-greater-element-iii_description]: https://leetcode-cn.com/problems/next-greater-element-iii/description/