<p>你的算法太简单了。您有一个正确的想法,检查前一个元素小于后一个元素但需要更多元素的连续元素对。</p>
<p>制作一个例程<code>first_bad_pair(sequence)</code>,它检查所有元素对的顺序列表。如果是,则返回值<code>-1</code>。否则,返回前面元素的索引:这将是一个从<code>0</code>到<code>n-2</code>的值。然后一个可行的算法就是检查原始列表。如果可以的话,可以,但是如果不能的话,试着删除前面或者后面的有问题的元素。如果其中任何一个工作,好,否则就不好。</p>
<p>我可以想到其他算法,但这一个似乎是最直接的。如果您不喜欢通过组合原始列表的两个片段而生成的最多两个临时列表,则可以使用更多的<code>if</code>语句在原始列表中进行比较来完成等效的操作。</p>
<p>下面是通过您显示的所有测试的Python代码。</p>
<pre><code>def first_bad_pair(sequence):
"""Return the first index of a pair of elements where the earlier
element is not less than the later elements. If no such pair
exists, return -1."""
for i in range(len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
</code></pre>
<p>如果您确实想避免这些临时列表,这里还有其他代码有一个更复杂的对检查例程。</p>
<pre><code>def first_bad_pair(sequence, k):
"""Return the first index of a pair of elements in sequence[]
for indices k-1, k+1, k+2, k+3, ... where the earlier element is
not less than the later element. If no such pair exists, return -1."""
if 0 < k < len(sequence) - 1:
if sequence[k-1] >= sequence[k+1]:
return k-1
for i in range(k+1, len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence, -1)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence, j) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence, j+1) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
</code></pre>
<p>这是我做的测试。</p>
<pre><code>print('\nThese should be True.')
print(almostIncreasingSequence([]))
print(almostIncreasingSequence([1]))
print(almostIncreasingSequence([1, 2]))
print(almostIncreasingSequence([1, 2, 3]))
print(almostIncreasingSequence([1, 3, 2]))
print(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))
print(almostIncreasingSequence([0, -2, 5, 6]))
print(almostIncreasingSequence([1, 1]))
print(almostIncreasingSequence([1, 2, 3, 4, 3, 6]))
print(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))
print(almostIncreasingSequence([1, 2, 2, 3]))
print('\nThese should be False.')
print(almostIncreasingSequence([1, 3, 2, 1]))
print(almostIncreasingSequence([3, 2, 1]))
print(almostIncreasingSequence([1, 1, 1]))
</code></pre>