CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

    • 贪心算法理论基础
    • 找零
    • 柠檬水找零
    • 分发饼干
    • K 次取反后最大化的数组和
    • 加油站
    • 分发糖果
    • 根据身高重建队列
    • 划分字母区间
    • 单调递增的数字
      • 📃 题目描述
      • 🔔 解题思路
        • 暴力解法
        • 贪心算法
    • 监控二叉树
    • 使数组变成交替数组的最少操作数
    • 剑指 Offer 14- II - 剪绳子 II
    • 区间调度问题

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 贪心算法
小牛肉
2022-03-20
目录

单调递增的数字

# 📃 题目描述

题目链接:738. 单调递增的数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

# 🔔 解题思路

和 31. 下一个排列 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 有点像,不过这题好像更简单点

# 暴力解法

暴力解法,将 N 不断缩小,每减小一个就判断一次是否数字是递增排序的,如果是,则直接返回

class Solution {
    public int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i --) {
            if (checkNum(i)) {
                return i;
            }
        }
        return 0;
    }
	
    // 判断数字 i 的每位是否是递增的
    private boolean checkNum(int i) {
        int maxNum = 10;
        while (i != 0) {
            int temp = i % 10;
            if (temp <= maxNum) {
                maxNum = temp;
                i /= 10;
            }
            else {
                return false;
            }
        }
        return true;
    }
}

时间复杂度 O(N * M),M 是数字 N 的长度,LeetCode 上提交会超时

# 贪心算法

题目需要找出小于或等于 n 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

也就是说,如果这个 n 的各个位已经是单调递增的了(前一位小于后一位),那么就要不进行任何改变

换句话说,我们要考虑的其实就是前一位比后一位大的情况:

  • 局部最优:遇到 n[i - 1] > n[i]的情况,让 n[i - 1]--,然后 n[i] 直接赋值为 9,可以保证这两位变成最大单调递增整数。
  • 全局最优:得到小于等于 n 的最大单调递增的整数

从前后向遍历会改变已经处理的结果,所以我们需要从后往前遍历

举个例子:

322 -> 322 -> 292

可以看到,有可能出现前一个数和后一个数相同的情况,这种情况下是符合题意的,但是如果我们不进行处理,就会出现这个例子的情况。这里最后的 2 也应该变成 9

所以我们需要一个标志位 flag,来表示 flag 及之后的数都需要变为 9,比如这个例子中的 flag 就是 1,表示下标 1 以及其之后的数,都得变成 9.

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] chars = Integer.toString(n).toCharArray();
        // flag 及之后的数都需要变为 9
        int flag = chars.length; 
        for (int i = chars.length - 1; i > 0; i --) {
            if (chars[i - 1] > chars[i]) {
                chars[i - 1] -= 1;
                flag = i;
            }
        }
		
        if (flag == arr.length) {
            return n;
        }
       
        for (; flag < chars.length; flag ++) {
            chars[flag] = '9';
        }

        // 处理 09xxx 的情况,去掉开头的 0
        if (chars[0] == '0' && chars.length > 1) {
            char[] res = new char[chars.length - 1];
            int index = 0;
            for (int i = 1; i < chars.length; i ++) {
                res[index ++] = chars[i];
            }
            return Integer.parseInt(String.valueOf(res));
        }

        return Integer.parseInt(String.valueOf(chars));
    }
}

  • 空间复杂度:O(N)
  • 时间复杂度:O(N)

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
划分字母区间
监控二叉树

← 划分字母区间 监控二叉树→

最近更新
01
关于编程满天星
02
让我来告诉你 Java 程序员是怎么一步一步从入行到被裁的
06-08
03
Vision Pro,未来已来
06-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式