LeetCode 1243 - Array Transformation

https://www.cnblogs.com/seyjs/p/11785282.html

Given an initial array arr, every day you produce a new array using the array of the previous day.

On the i-th day, you do the following operations on the array of day i-1 to produce the array of day i:

1. If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
2. If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
3. The first and last elements never change.

After some days, the array does not change. Return that final array.

Example 1:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]
Explanation: 
On the first day, the array is changed from [6,2,3,4] to [6,3,3,4].
No more operations can be done to this array.

Example 2:

Input: arr = [1,6,3,4,3,5]
Output: [1,4,4,4,4,5]
Explanation: 
On the first day, the array is changed from [1,6,3,4,3,5] to [1,5,4,3,4,5].
On the second day, the array is changed from [1,5,4,3,4,5] to [1,4,4,4,4,5].
No more operations can be done to this array.

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 100

https://dongweidotblog.wordpress.com/2019/11/04/1243-array-transformation/
解题思路：概括以下题目的意思，根据前一个的数组状态来更新当前状态，所以需要有一个数组来保存前一个状态中每一个元素的变化值，每次都需要提前更新，如果没有变化则直接返回答案。

时间复杂度 O(n) / 空间复杂度 O(n)
    vector<int> transformArray(vector<int>& arr) {
        vector<int> adder(arr.size(), 0);
        bool flag = true;
        while(flag){
            flag = false;
            for(int i = 1; i < arr.size() - 1; ++i){
                arr[i] += adder[i];
                adder[i] = 0;
            }
            for(int i = 1; i < arr.size() - 1; ++i){
                if(arr[i - 1] < arr[i] && arr[i] > arr[i + 1]){
                    flag = true;
                    adder[i] = -1;
                }
                if(arr[i - 1] > arr[i] && arr[i] < arr[i + 1]){
                    flag = true;
                    adder[i] = 1;
                }
            }
        }
        return arr;
    }

https://www.acwing.com/solution/LeetCode/content/5792/

(暴力模拟) $O(100{\mathrm{n^}}^2)$

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

时间复杂度

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

空间复杂度

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

    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;
    }