556. Next Greater Element III

这道题要是有想法,还是能解决的。
题目要求:大约num,但是是大于num中最小的。同时数字个数和num一样。(要增加的最少)

例如,654321,就不存在。
3245321,对于从后往前递增部分,不存在更大的,因此无法修改。
但是对于非递增部分,第一个 4, 是可以修订的部分,要修订为【5,3,2,1】中,第一个大于4的值,也就是5.然后将4,5交互,3254321,大于num了,但不是大于中最小的,5不能动,5之后的4321从排序,1234, 3241234就是最后的结果。

class Solution {
public:
    
    bool isint(string num){
        string maxnum = "2147483647";
        if (num.size() == maxnum.size()){
            if (num > maxnum){
                return false;
            }
            else{
                return true;
            }
        }
        else if (num.size() < maxnum.size()){
            return true;
        }
        else{
            return false;
        }
    }
    
    
    
    // 最小整数,和n数字相同,同时取值>n
    //12345 => 12354
    //12344 => 12434
    int nextGreaterElement(int n) {
        string num = to_string(n);
        int jj = num.size()-2;
        while(jj>=0&&num[jj]>=num[jj+1]){
            jj --;
        }
        if (jj==-1){ // already max
            return -1;
        }
        
        // find min >s[jj],must find
        int ii = 0;
        for(ii=num.size()-1;ii>=jj+1;ii--){
            if (num[ii]>num[jj]){
                break;
            }
        }
        
        //swapii,jj
        char ch = num[ii];
        num[ii] = num[jj];
        num[jj] = ch;
        
        // sort [jj+1, end]
        int start = jj+1;
        int end = num.size()-1;
        while(start<end){
            char ch = num[start];
            num[start] = num[end];
            num[end] = ch;
            start++;
            end--;
        }

        if (isint(num)){
            return atoi(num.c_str());
        }
        else{
            return -1;
        }
    }
};
上一篇:[LeetCode] 556. Next Greater Element III


下一篇:LeetCode 556. 下一个更大元素 III(Next Greater Element III)