题目描述： 给你一个整数数列a1,a2,a3,…,an,请你修改（不能删除，只能修改）最少的数字，使得数列严格单调递增。 数列存储在列表L中，你可以直接使用L，L的长度小于100000。 注意：必须保证修改后的数列依然是整数序列，不能修改成小数。 例如：L=[1,3,2],则输出1 Note:数据已于2014-12-3加强， 原来能通过的代码可能无法再次通过。
示例： 输入： L = [1, 3, 2] 输出： 1
分析:
我们的目的是得到一个 严格单调递增的数列。因此：
只有两个数a， b时，如果后一个数大于前一个数(b>a)，那么我们不需要做任何的改变，否则我们需要有所改变。
如果后一个数小于等于前一个数(b <= a)的时候，我们肯定是要做一次修改的。
只有两种修改的方案：
修改后一个数。 b = a + 1
修改前一个数。 a = a’ + 1。 （a’ 为 a 前面的一个数）
那么问题就来了， 如果选择这两种方案呢？？思考一下。
首先我们最好是选择第2种方案，这样的话，b 后面的数才更加容易大于b。
那么什么时候选择第1种方案呢？ 思考一下。
当 b - a’ <= 1 的时候, 我们选择第一种方案. 因为 b - a’ > 1时可以得到 a = a’ + 1 即 a < b, 符合严格单调递增.
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 当第 1 个数开始判断的时候,它的前面没有数,为了避免后面的特殊判断, 初始化一个数.
L = [-1000000000] + L
len_L = len(L)
ans = 0
for i in range(2, len_L):
if L[i] > L[i-1]:
continue
ans += 1
if L[i] - L[i-2] > 1:
L[i-1] = L[i-2] + 1
else:
L[i] = L[i-1] + 1
print(ans)