letcode每日一题-单调递增的数字

落日映苍穹つ 2022-12-28 06:25 194阅读 0赞

题目描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]

根据题目的要求我们是要找出小于或等于 `N` 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调

递增。

# 方法一:当做数字处理+双向队列 #

应为我们没办法直接获得对应整数N的最高位，而能直接获得个位数（N%10）,所以我们从个位开始处理，应

为从最高位起是单调递增的，则从最最低位起应该是单调递减的，这样我们依次判断就好，如果符合递减就放入

双向队列中，如果不符合则应该清空原数组，放入当前数值-1，应为如果当前数字不满足单调递减，则最大的就

是当前数字-1，后面的拼9就可以了，例如42，2<4不满足递减，则满足题目要求的数字就是39。

特殊情况处理：

1.双向队列中的为<=0的元素，位于队首则是直接跳过即可，不需要处理

2.双向队列中的为<=0的元素，不位于队首则直接当做9拼入结果中

代码实现如下:

public int monotoneIncreasingDigits(int N) {
            int count=0;
            int n=N;
            Deque<Integer> stack=new LinkedList<>();
            while (n>0){
                if(!stack.isEmpty() && stack.peekFirst()<n%10){
                    stack.clear();
                    stack.push(n%10-1);
                }else {
                    stack.push(n%10);
                }
                count++;
                n=n/10;
            }
            if(stack.size()==count){
                return N;
            }
            int result=0;
            for(int i=0;i<count;i++){
                if(!stack.isEmpty()){
                    int tmp=stack.pollFirst();
                    if(tmp<=0 && i==0 ){
                        continue;
                    }else if(tmp<=0){
                        result=result*10+9;
                    }else {
                        result=result*10+tmp;
                    }
                    continue;
                }
                result=result*10+9;
            }
            return result;
        }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 1][]

# 方法二:贪心算法+转为字符数组 #

public int monotoneIncreasingDigits(int N) {
            char[] strN=String.valueOf(N).toCharArray();
            int i=1;
            for(;i<strN.length;i++){
                if(strN[i-1]>strN[i]){
                    break;
                }
            }
            if(i==strN.length){
                return N;
            }
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length; ++i) {
                strN[i] = '9';
            }
            return Integer.parseInt(new String(strN));
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/e5632648a3c64110870df06bbc5d300f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201215102747724.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201215103852134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ==,size_16,color_FFFFFF,t_70