京东笔试（离AK最近的一次，可惜）
首先就想吐槽下它那个破代码平台，真的烂
然后代码编辑器，真就是一张白纸，连main函数和导包都得自己写（好在右上角有个指南里面有个Demo，不然要是忘了Scanner要导那个包怕不是直接坐牢俩小时
题目方面，算法就两个，没有签到题，第一题就上强度，第二题反而简单一些，因为它是利特扣德上题目《滑动窗口最大值》的变体，做过原型的话基本上就不难想
第一题是给个数组，可以进行一次操作：选定一个区间使得区间内的值都+1。要求尽可能使此操作减少最多数量的逆序对，并返回所减少逆序对的数目
乍一看一点思路都没有，因为光是求取一个数组的逆序对数量就已经是一个hard（参见LCR.170）难度了，这还不包括后面处理最大化收益的逻辑。所以这题坑就坑在它完全不给你暴力的机会。
但注意到题目要求返回的是操作所减少的逆序对的数目（比如原数组5个逆序对操作后变成3个则返回2），所以实际上并不需要求操作前后的逆序对数量分别是多少，只需考虑如何将“受影响的逆序对数量”最大化即可。依照题目，假如我们对区间[L, R]进行操作，则可以把数组分为三部分：[0, L - 1]，[L, R]，[R + 1, len(arr)]
而中间[L, R]这一段集体+1的操作，对其中每个的x∈[L, R]，都会带来 a = count(y, y∈[0, L - 1] & y = x + 1) 个逆序对的减少，但与此同时也会额外增加 b = count(z, z∈[R + 1, len(arr)] & z = x) 个逆序对。而我们要做的是确定这样的一个区间，使 a - b 最大化
显然这样做非常困难，但这个问题是否可以简化一下呢？当然。实际上我们从一开始就掉入了这个题干中的陷阱。事实上并不用选择一个[L, R]区间来进行操作——我们完全可以在任何情况下都贪心地把L之后的元素全部选择：因为它们集体进行了+1，那么这个过程其内部就不会产生额外的逆序对。这样一来问题就简化为了，选定一个下标i，使得 count(i之前的元素 = i及其之后的元素 + 1) 最大化。
实现方面，朴素解法是对于每个下标i都去遍历一遍整个数组，全量计算满足条件的元素对个数，开销是n^2。这里可以使用两个HashMap去算增量，从而将时间开销优化至o(n)通过全部用例，关键部分代码如下：
public int f(int[] arr) {
Map<Integer, Integer> leftNums = new HashMap<>();
Map<Integer, Integer> rightNums = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
rightNums.put(num, rightNums.getOrDefault(num, 0) + 1); // 一开始全部都在右侧集合
}
int ans = 0;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
rightNums.put(num, rightNums.get(num) - 1); // 元素离开右侧集合
sum -= leftNums.getOrDefault(num + 1, 0); // 元素原先作为右侧集合元素被计算的逆序对数量被扣除
leftNums.put(num, leftNums.getOrDefault(num, 0) + 1); // 元素进入左侧集合
sum += rightNums.getOrDefault(num - 1, 0); // 计算右侧集合中比该元素小1的元素的个数
ans = Math.max(ans, sum);
}
return ans;
}
第二题是给定一个数组和一个窗口长度，窗口的分值计算规则是：窗口内所有元素去掉一个最高分和一个最低分，其余元素的均值。返回分数最高的窗口的起始下标
这个就不想多做解释了，本质上就是滑动窗口最大值的变体，只是这次需要同时维护最大值和最小值，可以通过两个单调队列来实现。此外还需要增量式地维护每个窗口的总分，然后从两个队列中peek出最高分和最低分减去，再和历史最大值比较即可。注意窗口总分需要使用长整型避免溢出。代码比较冗长这里就不贴了，具体可以去利特寇德上看原型题
（不过不知道为啥我这里无论怎么提交都只过91%的用例，一直到交卷也没找出哪个边界case有问题，可能确实是有些细节没考虑到吧
投递美团等公司10个岗位