题目描述

首先，给你一个初始数组 arr。然后，每天你都要根据前一天的数组生成一个新的数组。

第 i 天所生成的数组，是由你对第 i-1 天的数组进行如下操作所得的：

• 假如一个元素小于它的左右邻居，那么该元素自增 1。
• 假如一个元素大于它的左右邻居，那么该元素自减 1。
• 首、尾元素永不改变。

过些时日，你会发现数组将会不再发生变化，请返回最终所得到的数组。

样例

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

输入：[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 <= arr.length <= 100
• 1 <= arr[i] <= 100

算法

(暴力模拟) $O(100n^2)$

1. 按照题目描述暴力模拟，直到数组不再变化。

时间复杂度

• 每个数字最多改变 100 次，共有 $n$ 个数字，每轮迭代需要 $O(n)$ 的时间。
• 故时间复杂度为 $O(100n^2)$。

空间复杂度

• 需要 $O(n)$ 的空间作为辅助数组。

C++ 代码

class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        int n = arr.size();
        vector<int> pre(arr.begin(), arr.end());
        bool flag = true;
        while (flag) {
            for (int i = 1; i < n - 1; i++) {
                if (pre[i - 1] < pre[i] && pre[i] > pre[i + 1])
                    arr[i]--;
                if (pre[i - 1] > pre[i] && pre[i] < pre[i + 1])
                    arr[i]++;
            }
            flag = false;
            for (int i = 0; i < n; i++)
                if (pre[i] != arr[i]) {
                    pre[i] = arr[i];
                    flag = true;
                }
        }
        return arr;
    }
};