面试题分享

Zerol 跟我分享了几题面试题，我记录一下，都是直接说答案了，分析过程从简。

有一个数组，每一个元素都是一个整数，现在要你寻找一个 ii 和 jj 满足，i<ji<j 且 ai<ajai<aj 并使得 aj–aiaj–ai 最大。

如果 jj 固定了，那么就是其实是从它之前的元素中找到一个最小的。

最小值显然容易维护，而且对于所有的 jj，都只要维护一个最小值就可以了。

维护一个最小值，扫一遍，对于每一个 jj，都计算它和最小值的差值，如果遇到更小的值则更新最小值。

开胃菜结束。

上题换成并使得 aj–aiaj–ai 最小。

O(n2)O(n2) 的显然可以。

方法一：

如果给定一个 ii，就是从它右边的元素中，找一个大于它的，但是和它最接近的。

如果把 aiai 右边的元素全部排序，那么找到第一个大于 aiai 的元素，将他们最差即可。

假设我已经有了 aiai 右边的所有元素从小到大排列（事实上，重复元素可以舍去，因为只关心差值，那么对于重复的元素是没有必要区分的），那么直接用类似二分的方法就可以找到需要的元素。

对于任意的 ii，重复上面的过程。

如果每次都是从列表中取出 aiai 右边的元素再排序，太慢了。

注意到如果扫的顺序是固定的，那么一开始显然 Set 为空，随着扫描的进行，对于某一个元素，我可以从 Set 中找到第一个大于它的元素，作差记录，然后把这个元素放入到 Set 中，对于下一个元素，继续从 Set 中（此时 Set 中元素的个数可能多了一个，也可能由于去重以后不变）找到第一个大于它的元素，作差记录、比较、留最小的差，然后把这个元素放入到 Set 中……

C++ 可以用 upper_bound() 或者 lower_bound()，取决于从哪里扫，都是一样的。

Java 中可以用 TreeSet，肯定是一棵类似红黑树的结构，而由于 TreeSet 没法用 Collection.binarySearch()，但是幸运的是（其实我也是今天才知道）可以用 ts.higher()、ts.ceiling()、ts.lower()、ts.floor()，至于 heigher 和 ceiling 有什么区别、lower 和 floor 有什么区别，看为文档，至于为什么叫 higher 不叫 upper，我不知道。

方法二：

分治。

用归并排序，做逆序对的思想。

分治以后，数组就是有序的。

同时我记录下是来自于左边一半还是右边一半。

然后扫一遍，如果当前元素来自于左边，就始终更新成最后出现的那个左边元素的值，如果来自于右边，就与维护的那个最后的左边相减。

方法三：

排序，从小到大，但是保留原来的下标。

只需要考虑新数组中相邻两数的差即可。

遍历数组，如果相邻两数的原下标满足 i<ji<j，那么作差。

有一个全部是 0 或者 1 组成的序列，你可以任选一段区间进行变换操作，变换指的是把所有的 0 变成 1 同时把所有的 1 变成 0。

例如，0 0 1 1 0 1，可以选择变更 1 1 0 1 为 0 0 1 0，也可以选择变更 1 1 为 0 0，这两种做法都是会使得 0 的个数最大。

输入任意一个区间的起始和结束，使得对该区间变换后，0 个数最大。

我的第一思路是，遇到 0 就加 1，遇到 1 就减 1。

例如对于上面的样例：

0   0   1   1   0   1   0   1   1
-1  -2  -1  0   -1  0   -1  0   1

然后注意到

0   0   1   1   0   1   0   1   1
-1  -2  -1  0   -1  0   -1  0   1
        1   2   1   2   1   2   3

所以可以找到区间。

然而要证明，我不会。

但是当我写下上面 2 行的时候，zerol 突然意识到——哦，我知道为什么让我证明正确性的时候那么复杂了，其实只要把 0 看成 1，把 1 看成 -1，然后计算前缀和，维护一次差分，就变成了刚才那个问题，就是找到一个 aiai和 ajaj 使得差值最大，就是令区间中 1 的个数和 0 的个数的差值最大，是一样的。

好的，那就完成证明了。

最大子段和。