2018 Bronze February p3

题目

John 有一个计数器，记录从某次越狱开始每天距离上次奶牛越狱的天数（越狱当天为0）。当他打算统计时，计数器上某些天数被涂掉了（用 -1 表示）。给出总天数 N 和每天记录的天数，返回 N 天中奶牛越狱次数可能的最小值和最大值，若记录的天数有矛盾的地方，返回 -1

思路

根据题目，第一天的数字一定为 0。将记录计数的数组复制一份，原数组用于参考数据，并在新数组上进行更改。从后往前遍历原数组，每当发现一个不为 -1 的元素 m，在新数组中将该元素前 m 个元素更改为相应的降序数字，过程中若发现矛盾，返回 -1。遍历完成后，新数组中 0 的数量即为越狱次数的最小值，0 与 -1 的总数量为最大值

复杂度分析

由于只需要遍历一次数组，时间复杂度为 O(n)，且 N 最大为 100，不会超时