这个问题的最优算法是什么?

假设你有一个数组 A 属于 N 整数。在一轮中,您将进行如下更改(基于本轮开始时的阵列快照):

• -=1,如果大于两个相邻的(在两侧)
• +=1,如果小于两个相邻的(在两侧)

边缘/末端的那个永远不会改变,当上一轮发生改变时,你会继续前进。

一个简单的算法看起来像:

    while True:
        prior = A
        cur = A[:]
        for i in range(1, len(cur) - 1):
            if prior[i - 1] > prior[i] and prior[i + 1] > prior[i]:
                cur[i] += 1
            elif prior[i - 1] < prior[i] and prior[i + 1] < prior[i]:
                cur[i] -= 1
        if cur == prior:
            break
        A = cur
    return A

这是我最近进行的一次编码评估。以下是几个例子:

Input: [1, 6, 3, 4, 3, 5]
Returns: [1, 4, 4, 4, 4, 5]

Input: [100, 50, 40, 30]
Returns: [100, 50, 40, 30]

第一种情况的解释:

1 和 5 结局永远不会改变,因为他们没有两个邻居。对于任何测试用例也是如此。下一个状态将如下,

[ 1, 5, 4, 3, 4, 5] 

• arr[2]=5,因为 1 < 6 > 3 , 6 减少1使其成功 5.

• arr[3]=4,因为 6 > 3 < 4 , 3 增加1使其成为 4 。

• arr[4]=3,因为 3 < 4 > 3 , 4. 减少1使其成功 3. 。

• arr[5]=4,因为 4 > 3 < 5 , 3. ,增加1使其成为 4. 。

  [ 1, 5, 4, 3, 4, 5] becomes [1, 4, 4, 4, 4, 5] in a similar fashion as above and stops here since no further operations can be performed.
  

第二种情况的解释:

没有对阵列采取任何行动,因为没有一个非边界元素具有较小或较大的邻居。