738. 单调递增的数字

From
Leetcode
Status
回头复习下
Date
Mar 29, 2024
Tags
贪心算法
Difficulty
中等
Link
https://leetcode.cn/problems/monotone-increasing-digits/description/

题面

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
示例 2:
示例 3:
提示:
  • 0 <= n <= 109
 

思路

从后往前遍历，每当前一位更小时，前一位减一，后面所有数变为9
 

题解

暴力 O(n × m） 超出时间限制

Loading...