1243. Array Transformation

解题思路：概括以下题目的意思，根据前一个的数组状态来更新当前状态，所以需要有一个数组来保存前一个状态中每一个元素的变化值，每次都需要提前更新，如果没有变化则直接返回答案。

时间复杂度 O(n) / 空间复杂度 O(n)

class Solution {
public:
    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;
    }
};