目标
小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。
主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。
由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。
思路
老实说这道题我花了好一会儿才弄清楚题目要求，最后解法还因为超时没有通过。
先解释一下目标吧，实际上需要求解的是每一个位置上的局部最优解。所谓局部指仅考虑当前位置及之前的所有位置的操作次数。所谓最优是指初始序列达到满足条件的状态（公差为1的等差数列）时所做操作总和的最小值。如果有N个计数器，那么就有N个满足条件的序列，有可能前面操作最少的序列并不是后面操作最少的序列，即前面位置的总操作次数可能并不是当前最优解的一部分。可以参考上面图片的示例3。
我的思路就是直接暴力破解，循环遍历输入的数组，在第i次遍历中，分别将（0 ~ i-1）位置上的元素作为基点k，左侧的序列依次减1，右侧的依次加1。在第k个序列中求解（0 ~ i-1）位置上操作次数的累加和。在第j个位置上的操作次数为 nums[k]-(k-j)。
代码
public static int[] numsGame2(int[] nums) {
int[] res = new int[nums.length];
// 累加k序列的操作总和
int[] acc = new int[nums.length];
for (int i = 1; i < nums.length; i++) {
for (int k = 0; k <= i; k++) {
int temp = acc[k];
// 增加一些判断跳过一些计算
if(temp >= res[i] && res[i] != 0){
continue;
}
// 这里看似套了3个循环，但其实只有在k序列第一次出现时才会循环i次，那么前面的i-1次只需从acc中累计即可，实际时间复杂度是O(n^2)
for (int j = temp == 0 ? 0 : i; j <= i; j++) {
temp += Math.abs(nums[j] - (nums[k] - (k - j)));
}
acc[k] = temp;
if (k == 0) {
res[i] = temp;
} else {
res[i] = Math.min(res[i], temp);
}
}
res[i] = res[i] % 1000000007;
}
return res;
}| acc | a | b | c | d |
|---|---|---|---|---|
| acc[0] | 0 | |b-a-1| | |c-a-2| | |d-a-3\ |
| acc[1] | |a-b+1| | 0 | |c-b-1| | |d-b-2\ |
| acc[2] | |a-c+2| | |b-c+1| | 0 | |d-c-1\ |
| acc[3] | |a-d+3| | |b-d+2| | |c-d+1| | 0 |
如上表所示，如果序列是[a,b,c,d]，基点k等于c的时候，前2次从acc累加，最后一次需要重新累加。时间复杂度为O(n^2)。这和我们常见的外层循环N次，内层循环N次不同。循环的计算次数序列为1、3、5、7...，根据等差数列求和公式：Sn = n × a1 + (n × (n-1)/2) × d，当 d=2，a1=1 时，Sn = n^2。
性能
由于题目给出的数组最大长度是10^5，暴力求解是不可行的。也尝试了增加条件判断跳过一些计算但还是无法降低问题的规模。于是就开始怀疑是否前面的计算结果是否与后面的计算有关联，可以简化后面的计算？更优的算法复杂度应为O(nlogn)、O(logn) 和 O(n)。我思考了很久，应该是存在知识盲区了。我去看了答案，涉及到求中位数。其实一开始有想过中位数，方差均值这些，但是没想到和这个最优解有什么关系。今天没时间了，抽空再看看吧。
