计算通过删除一项来进行排序的方式数量

Question

我最近遇到了一个基本上是以下问题的变体的问题：

我们想通过从数组中精确删除一项来使数组以非降序排序。我们有多少种方法可以做到？

例如，如果输入数组为[3, 4, 5, 4]，则答案为2，因为我们可以删除其中一个5或第二个4。

如果数组是[3, 4, 5, 2]答案1，则可以删除2。

如果数组是[1, 2, 3, 4, 5]答案，将是5，因为我们可以删除任何一个元素。

我正在努力解决这个问题。有关解决方案策略的任何指示/方向将不胜感激。

Answer 1

您提供的示例已经涵盖了大多数情况；答案始终是0、1、2或N，并且您应该能够通过对序列进行一次迭代来找到解决方案。

从左到右遍历数组，寻找成对的相邻元素，其中左元素大于右元素。

如果您未找到递减对而到达序列的末尾，则该序列已经是非递减的，答案为N。

如果找到递减对，请检查删除左元素是否有效，即其前面的元素是否不大于右元素，然后检查删除右元素是否有效，即左元素是否不大于该元素在正确的元素之后。

如果这两个选项都不起作用，则可以返回答案0，因为不可能使序列不减小；否则，就不能返回0。例如[2,2,1,1]。

如果其中一个或两个选项有效，请继续检查其余序列；否则，请继续进行操作。如果找到另一个递减对，则答案变为0（不可能）。

用伪代码：

options = 0
for i is 1 to array.length - 1
    if array[i-1] > array[i]
        if options is not 0
            return 0
        if i is 1 or array[i-2] <= array[i]
            ++options
        if i is array.length - 1 or array[i-1] <= array[i+1]
            ++options
        if options is 0
            return 0
if options is 0
    options = array.length
return options

或翻译成简单的Javascript代码段：

options = 0
for i is 1 to array.length - 1
    if array[i-1] > array[i]
        if options is not 0
            return 0
        if i is 1 or array[i-2] <= array[i]
            ++options
        if i is array.length - 1 or array[i-1] <= array[i+1]
            ++options
        if options is 0
            return 0
if options is 0
    options = array.length
return options