Min Amplitude

这是一道google的oa题, 给一个数组, 通过改变三个数后, 使得数组最大值和最小值的差, 最小.

狗家的题都是先观察, 然后再coding, 主要是找到好的思路. 这题也是这样, 首先观察我们可以使用的操作, 就是改变数组中任意的三个数. 因为最后求最值的差, 所以这三个数的选择肯定是选择和最值有关的数. 首先排序一下, 然后找到两头(最大数列,和最小数列). 发现因为只有三个数可以改变, 那么改变后的最值肯定出在以下几种情况: 改变了最小的三个值, 答案= 第四小的值与最大值的差…由此类推即可发现答案有四种可能.

具体实现上, 因为要找到最大的四个数和最小的四个数, 可以sort, 也可以用priority queue.