[3,4,2,3]
的测试用例会无法通过。问题在于递减对的计算方式有问题。[3,4,2,3]
来说,其递减对不仅仅有 (4,2)。其实应该还包括 (4,3)。 这提示我们在这个时候应该将 2 修改为不小于前一项的数,也就是 4,此时数组为 [3,4,4,3]
。这样后续判断就会多一个(4,3) 递减对。[3,4,3,3]
,在这个例子中应该将索引为 1 的修改为 3,即 [3,3,3,3],而不是将索引为 2 的修改为 4,因为末尾数字越小,对形成递增序列越有利,这就是贪心的思想。代码上,我们没有必要修改前一项,而是假设 ta 已经被修改了即可。之所以可以假设被修改是因为题目只需要返回是否可组成非递减数列,而不需要返回具体的非递减数列是什么,这一点需要大家注意。[4,2,3] [4,2,1] [1,2,1,2] [1,1,1,] []
。这样就可以写代码了。