个人中心
文章发布
退出
作者热门文章
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
24
4
题目地址：https://leetcode.com/problems/monotone-increasing-digits/description/
Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.
(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)
Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].
找出一个比这个数字小的，每位数字都是递增的最大数字。
把题目给出的数字拆分成数组进行理解。如果这么理解之后，那我们就是要找到一个最大的递增数组。
做的方法是找出第一个降序的位置，有两种情况：
case 1: 对于 14267 , 第一个出现下降的位置是4，所以把4变成3，把4后面的数字全部改成9.得到13999；
case 2: 对于1444267, 第一个降序的位置是最后一个4，如果只把最后一个4按照case1处理，那么得到的是1443999，仍然不满足题意。所以需要找到第一个位置的4，然后做case1操作，这样得到的是1399999。
写代码的时候我是逆序过来做的，然后我犯了一个错误，写成了num[i] > num[i - 1] or (ind != -1 and num[i] == num[i - 1])。为什么不能是num[i] == num[i - 1]呢？因为这样会找到最后的一个相等的位置，而我们只需要找到最先出现相等的位置即可。
时间复杂度是O(n)，空间复杂度是O(n).
代码如下：
class Solution:
def monotoneIncreasingDigits(self, N):
"""
:type N: int
:rtype: int
"""
if N < 10: return N
num = [int(n) for n in str(N)[::-1]]
n = len(num)
ind = -1
for i in range(1, n):
if num[i] > num[i - 1] or (ind != -1 and num[i] == num[ind]):
ind = i
if ind == -1:
return N
res = '9' * ind + str(num[ind] - 1) + "".join(map(str, num[ind + 1:]))
return int(res[::-1])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
如果不使用逆序，也可以做：
class Solution:
def monotoneIncreasingDigits(self, N):
"""
:type N: int
:rtype: int
"""
if N < 10: return N
num = [int(n) for n in str(N)]
n = len(num)
ind = n - 1
for i in range(n - 2, -1, -1):
if num[i] > num[i + 1] or (ind != n - 1 and num[i] == num[ind]):
ind = i
if ind == n - 1:
return N
num[ind] -= 1
for i in range(ind + 1, n):
num[i] = 9
return int("".join(map(str, num)))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
参考资料：
https://leetcode.com/problems/monotone-increasing-digits/discuss/109794/Simple-Python-solution-w-Explanation
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
24
4
0
情况 我正在尝试熟悉 Java 中的线程。出于这个原因，我修改了我在一本书中找到的程序列表。所做的事情非常简单: 它创建一个包含 100.000.000 个元素的 boolean[] 数组。 它使用
我正在使用 Zurb Foundation 使用以下代码制作导航栏:
Write a program that reads a sequence of integers and print 'increasing' if each subsequent number i
我有比特币源代码(多线程)，我打算添加一些新行。在比特币网络上，数据消息在数据存储在 vector 中的地方交换。我想在 vector 大小增加时执行一些指令: 如何在 C++ 中编写以下模式以便在
We are given a network flow, as well as a max flow in the network. An edge would be called increasin
我想增加 Line2D 的宽度。我找不到任何方法来做到这一点。我是否需要为此实际制作一个小矩形？ 最佳答案 您应该使用 setStroke 来设置 Graphics2D 对象的笔画。 http://w
题目地址：https://leetcode.com/problems/increasing-triplet-subsequence/description/ 题目描述： Given an unso
题目地址：https://leetcode.com/problems/longest-increasing-subsequence/description/ 题目描述 Given an unsor
题目地址：https://leetcode.com/problems/monotone-increasing-digits/description/ 题目描述： Given a non-negat
我已经从头开始实现逻辑回归，但是当我运行脚本时，算法总是预测错误的标签。我尝试通过将所有 1 切换为 0 来更改训练输出和 test_output，反之亦然，但它总是预测错误的标签。 我还注意到，将“
我正在尝试增加kivyMD 按钮 的宽度 和高度，但它不受支持(size_hint)。 •我应该创建自己的继承自 Button 类的按钮类吗？ •考虑到我希望我的应用程序在 Android 上运行，这
ArrayList tempArray = new ArrayList<>(size); 我正在为我的合并排序构建一个 tempArray，它将根据上下文对整数或字符串进行排序。因此类型为 T Arr
我正在尝试创建大约200万条记录的Lucene。索引时间约为9小时。 您能否建议如何提高性能？ 最佳答案 我写了一篇关于如何并行化Lucene索引的可怕文章。它确实写得很糟糕，但是您会发现它是here
我需要你的帮助来解决这个问题 这是我的 ulimit -a 的结果在我的 linux 服务器上 core file size (blocks, -c) 0 scheduling
我想了解: 与完全虚拟化或硬件辅助虚拟化(如 virtio_net 或 virtio_blk)相比，virtio 驱动程序如何提高性能？ 这些 virtio 驱动程序如何影响 VMEXIT/VMENT
我正在使用 rose2.m 生成许多角度直方图。我希望显示每个箱子中元素数量的比例范围在 0-50 之间，对于所有地 block 以 10 为增量增加，即使特定地 block 上的最大元素数量小于 5
我正在为我使用远程音频单元的 iPhone 构建一个录音应用程序。在对传入缓冲区执行一些音频分析后，我使用以下方法将缓冲区写入磁盘: ExtAudioFileWriteAsync 但是，我遇到的问题是
您好，我正在解析 xml 文件，我正在返回 Objects 类的 ArrayList，但是对于此方法的每次调用，ArrayList 的大小为从 0-8 和 8 增加到 16 和 24...而不是创建一
在一些 Django 测试中，我有循环来测试很多东西。 在最终结果中它显示为: Ran 1 test in 3.456s 我想为每个循环增加该计数器，我该怎么做？ 它正在使用 subTest() ，但
我正在努力解决这个指针算术: int x; int *y = &x; ++y; y 增加了多少？ 我知道:“&”是引用运算符，可以读作“address of”。“*”是解引用运算符，可以读作“指向的值
我是一名优秀的程序员,十分优秀！