月薪一万、双休、五险一金，但办公室没同事，你能坚持几年？附数组严格递增题解

刚刷到这个，给我看乐了。

一万块，双休，五险一金，办公室还就你一个人。网友居然纠结“没人唠嗑，能干几年”。这还用问？我能干到公司倒闭，干到老板求我回家，干到太阳系关服。

没人聊天算啥缺点啊，没人突然拍你肩膀问进度，没人开会开到下班，没人顺手把活甩你桌上。中午想吃啥吃啥，累了起来溜达两圈，也不用看谁脸色。

真待久了，最多就是有点安静。买个耳机，养盆绿植，实在憋不住就跟保洁阿姨聊两句。

这种班别问能干几年，先把公司地址发出来，晚一步都怕被别人抢了。

---

今日面试题

数组改成严格递增，别上来就排序

数组是：

[3, 2, 5, 5]

要求通过若干次加一操作，把它改成严格递增数组，并计算最少需要操作多少次。

这题第一眼容易想到排序。排序确实能让数字有序，但这里不能调整元素位置，只能给某个元素加一。原数组里谁在前、谁在后，不能动。

所谓严格递增，条件也很直接：

nums[i] > nums[i - 1]

注意是大于，不是大于等于。

像下面这个数组就不行：

[1, 2, 2, 4]

第三个元素和前一个元素相等，必须至少加一次，变成 3。

这题我一般直接从左往右扫。当前位置如果已经比前一个数大，不处理；如果小于或等于前一个数，就把它抬到“前一个数加一”。

为什么只能抬到这个值？

假设前一个数是 7，当前位置是 3。为了满足严格递增，当前位置最少必须变成 8。改成 9、10 当然也可以，但多做了操作，还会抬高后面元素需要达到的下限，纯属给自己加活。

拿 [3, 2, 5, 5] 走一遍。

第一个数 3 不动。

第二个数是 2，它不比 3 大，只能改成 4，需要两次操作。

数组相当于变成：

[3, 4, 5, 5]

第三个数 5 比 4 大，不处理。

最后一个数也是 5，和前一个数相等，需要改成 6，再加一次。

最终一共操作三次。

Java代码不需要真把数组每个位置都改掉，记录“前一个元素调整后的值”就够了：

public class StrictIncreaseCounter {

    public static long countOperations(int[] numbers) {
        if (numbers == null || numbers.length < 2) {
            return 0L;
        }

        long operations = 0L;
        long previous = numbers[0];

        for (int index = 1; index < numbers.length; index++) {
            long current = numbers[index];

            if (current > previous) {
                previous = current;
                continue;
            }

            long adjusted = previous + 1;
            operations += adjusted - current;
            previous = adjusted;
        }

        return operations;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 2, 5, 5};
        System.out.println(countOperations(numbers));
    }
}

输出结果：

3

代码里 previous 和 operations 我用了 long。数组元素虽然是 int，但连续调整时可能出现 previous + 1，操作次数累加后也可能超过 int。这种边界问题在 算法题 里未必每次都卡，工作代码里我不太愿意赌。

再看一个下降数组：

[5, 4, 3]

第二个数要从 4 调整成 6，需要两次。

第三个数不能只调整成 5，因为它前面的数已经变成了 6，所以必须调整成 7，需要四次。

总操作次数是六次。

这里有个容易写错的地方：比较的不是当前位置和原数组中的前一个值，而是和“调整后的前一个值”比较。前面的元素一旦被抬高，后面的最低值也会跟着抬高。

整个算法只扫描一次数组，时间复杂度是 O(n)，额外空间复杂度是 O(1)。

这题看着像数组模拟，真正需要抓住的只有一件事：每次只把当前元素调整到刚好合法的位置。多加一次都没有收益，反而可能让后面的调整更贵。