第4题-调整序列使其先递增后递减，求最小增加和

面试题目（贝壳笔试）：

给定一个数列，调整数列中的数值，使数列变成一个严格的先递增，后递减的数列（严格递增递减，是指相邻的数字不存在相等的情况，一定存在大小关系）。调整数值的时候，只能增加数值，求出满足严格递增递减数列的最小增加和。

示例：

1. 数列 [1, 2, 8, 8, 4, 3]，调整为严格递增递减数列后，最小增加和为1，此时数列变为[1, 2, 9, 8, 4, 3]。
2. 数列[1, 4, 2, 3, 5]，调整为严格递增递减数列后，最小增加和为6，此时数列变为[1, 4, 5, 6, 5]。

答案解析：

思路分析：

1. 该题的核心思想是要把数列变为一个严格递增递减数列，所以调整后数列中最大值的位置肯定在第二个和倒数第二个位置之间（2 ~ ary.length - 1）。
2. 假定最大值的位置，遍历数组，调整数列使其变成递增递减数列，求出增加和。
3. 严格递增递减数列有 ary.length - 2 种情况，求出最小的增加和即可。

实现代码：

var ary = [1, 4, 2, 3, 5];
function changeAry(ary) {
    var minSum = -1;
    for (var i = 1, len = ary.length; i < len - 1; i++) {
        var sum = 0;
        var tempAry = ary.concat();
        // 递增部分
        for (var m = 0; m < i; m++) {
            if (tempAry[m] >= tempAry[m + 1]) {
                var diff = tempAry[m] - tempAry[m + 1];
                tempAry [m + 1] += diff + 1;
                sum += diff + 1;
            }
            
        }

        // 递减部分
        for (var n = len - 1; n > i; n--) {
            if (tempAry[n] >= tempAry[n - 1]) {
                var diff = tempAry[n] - tempAry[n - 1];
                tempAry[n -1] += diff + 1;
                sum += diff + 1;
            }
        }

        if(i == 1) {
            minSum = sum;
            console.log(tempAry);
            console.log(minSum);
        } else {
            if(minSum > sum) {
                minSum = sum;
                console.log(tempAry);
                console.log(minSum);
            }
        }
        tempAry = null;
    }
}
changeAry(ary);

注意：

1. 代码中之所以要复制一份数组，是因为对数组值的改变，会影响下一次遍历。
2. Array.concat()方法，会复制数组得到副本，对副本的修改，不会影响原数组的值。

---

扫一扫 下方二维码，关注我的公众号【前端名狮】，更多精彩内容陪伴你！

【前端名狮】