---

1243. 数组变换

• 标签：数组、模拟
• 难度：简单

题目链接

• 1243. 数组变换 - 力扣

题目大意

描述：给定一个初始数组 $arr$。每天根据前一天的数组生成一个新数组，变化规则如下：

1. 如果一个元素小于它的左右邻居，该元素自增 $1$。
2. 如果一个元素大于它的左右邻居，该元素自减 $1$。
3. 首尾元素永不改变。

经过若干天后，数组不再变化（即某天生成的数组和前一天完全一样）。返回最终的数组。

要求：返回最终稳定的数组。

说明：

• $1 \le arr.length \le 10^{3}$。
• $1 \le arr[i] \le 10^{3}$。

示例：

• 示例 1：

输入：[6,2,3,4]
输出：[6,3,3,4]
解释：
第一天，数组从 [6,2,3,4] 变为 [6,3,3,4]。
无法再对该数组进行更多操作。

• 示例 2：

输入：[1,6,3,4,3,5]
输出：[1,4,4,4,4,5]
解释：
第一天，数组从 [1,6,3,4,3,5] 变为 [1,5,4,3,4,5]。
第二天，数组从 [1,5,4,3,4,5] 变为 [1,4,4,4,4,5]。
无法再对该数组进行更多操作。

解题思路

思路 1：模拟

1. 核心思想

这道题的规则可以想象成一个「拉平」过程：数组中的「尖峰」会被削低，「低谷」会被填高，而首尾两个位置不动。就像用一把刮刀反复刮过一根凹凸不平的木条，凸起的被削掉，凹陷的被填平，最终整个表面趋于平滑。

整个过程就是纯粹的模拟——按照题目描述的规则，一天一天地生成新数组，直到某一天数组不再变化为止。

2. 具体步骤

第 1 步：确定需要处理的范围

首尾元素永远不变，所以我们只需要关注下标 $1$ 到 $n-2$ 的元素（即中间元素）。

第 2 步：每轮生成新数组

每一轮（每一天）都基于当前的数组 $arr$ 生成一个新的数组 $new\_arr$：

• 先将当前数组复制一份给 $new\_arr$（首尾元素相同，不需要特殊处理）。
• 遍历下标 $1$ 到 $n-2$：
  • 如果 $arr[i] < arr[i-1]$ 且 $arr[i] < arr[i+1]$，说明当前元素是一个「低谷」，需要加 $1$：$new\_arr[i] = arr[i] + 1$。
  • 如果 $arr[i] > arr[i-1]$ 且 $arr[i] > arr[i+1]$，说明当前元素是一个「尖峰」，需要减 $1$：$new\_arr[i] = arr[i] - 1$。
  • 其他情况保持不变。

第 3 步：判断是否稳定

每轮结束后，检查 $new\_arr$ 是否和 $arr$ 完全相同。如果相同，说明数组已经稳定，直接返回 $new\_arr$。否则将 $arr$ 更新为 $new\_arr$，继续下一轮。

结合示例 2 走一遍：

初始数组：$[1,6,3,4,3,5]$

第一轮：

• $i=1$：$arr[1]=6$，左邻 $1$ 右邻 $3$，$6 > 1$ 且 $6 > 3$ → 减 $1$ → $5$
• $i=2$：$arr[2]=3$，左邻 $6$ 右邻 $4$，$3 < 6$ 且 $3 < 4$ → 加 $1$ → $4$
• $i=3$：$arr[3]=4$，左邻 $3$ 右邻 $3$，既不满足小于也不满足大于 → 不变 → $4$
• $i=4$：$arr[4]=3$，左邻 $4$ 右邻 $5$，$3 < 4$ 且 $3 < 5$ → 加 $1$ → $4$

结果：$[1,5,4,3,4,5]$，和原来不同，继续。

第二轮：

• $i=1$：$arr[1]=5$，左邻 $1$ 右邻 $4$，$5 > 1$ 且 $5 > 4$ → 减 $1$ → $4$
• $i=2$：$arr[2]=4$，左邻 $5$ 右邻 $3$，$4 < 5$ 且 $4 > 3$ → 既不小于也不大于 → 不变 → $4$
• $i=3$：$arr[3]=3$，左邻 $4$ 右邻 $4$，$3 < 4$ 且 $3 < 4$ → 加 $1$ → $4$
• $i=4$：$arr[4]=4$，左邻 $3$ 右邻 $5$，既不满足小于也不满足大于 → 不变 → $4$

结果：$[1,4,4,4,4,5]$，和原来不同，继续。

第三轮：遍历发现没有任何元素需要变化，$new\_arr$ 和 $arr$ 完全相同，返回 $[1,4,4,4,4,5]$。

思路 1：代码

class Solution:
    def transformArray(self, arr: List[int]) -> List[int]:
        n = len(arr)
        # 标记本轮是否有变化，没有变化说明已经稳定
        changed = True
        while changed:
            changed = False
            # 复制当前数组，首尾元素默认一致
            new_arr = arr[:]
            # 只处理中间元素（下标 1 到 n-2）
            for i in range(1, n - 1):
                if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
                    # 低谷：比两边都小，自增
                    new_arr[i] += 1
                    changed = True
                elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
                    # 尖峰：比两边都大，自减
                    new_arr[i] -= 1
                    changed = True
            # 更新数组，进入下一天
            arr = new_arr
        return arr

思路 1：复杂度分析

• 时间复杂度：$O(n \times d)$，其中 $n$ 是数组长度，$d$ 是数组变化所需的天数。每轮需要遍历一次数组的所有中间元素，需要 $d$ 轮才能达到稳定状态。最坏情况下 $d$ 可能接近 $n \times \max(arr)$，但对于本题的数据范围（$n \le 1000$，$arr[i] \le 1000$）来说是可以接受的。
• 空间复杂度：$O(n)$，每轮都需要创建一个新数组来保存变化后的结果。