求整数数组按规则迭代至稳态问题的更优算法

给定一个包含N个整数的数组A。每一轮中，基于本轮开始时的数组快照进行如下修改：

• 若元素大于左右两个相邻元素，则该元素减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

示例说明 #

示例1

输入: [1, 6, 3, 4, 3, 5]
输出: [1, 4, 4, 4, 4, 5]

位于两端的1和5因没有两个相邻元素，永远不会改变，所有测试用例均遵循此规则。第一轮迭代后的数组状态如下：

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

各元素变化原因：

• arr[1] = 5：因1 < 6 > 3，6减1变为5
• arr[2] = 4：因6 > 3 < 4，3加1变为4
• arr[3] = 3：因3 < 4 > 3，4减1变为3
• arr[4] = 4：因4 > 3 < 5，3加1变为4

继续迭代后，数组变为[1, 4, 4, 4, 4, 5]，此时无更多操作可执行，停止迭代。

示例2

输入: [100, 50, 40, 30]
输出: [100, 50, 40, 30]

数组无任何修改操作，因为所有非边界元素均不满足“左右相邻元素都更小或都更大”的条件。

现寻求解决该问题的更优算法。

内容的提问来源于stack exchange，提问作者user129393192