--- tags: 题解, 算法, --- # 题解：中位数金字塔 在原题的生成上一层的方法中，能发现一个关键的特点，如果某处连续出现两个相同的数，那么在这两数之上的层也一定是这两个数。 再做一下推广，如果相邻两数较小一个是p，较大的是q，那么在这两数之上的一定大于等于p小于等于q。 结合以上两个特性我们可以来一波二分的骚操作。 假定一个整数m，把原金字塔上的数字，小于等于m的转为0，大于m的转为1，通过求这个金字塔塔顶的数字，如果是0就知道是小于等于m，如果是1就是大于m，于是可以通过二分m的值来求解。 对于一个01组成的数组，怎么快速求解塔顶的数字呢？我们知道，如果某处连续两个相同的数，那么在这两数之上也一定是这两个数，那么，如果这两个数在塔尖的左边，那么比它们更左的数字不会影响最终结果，同理右则也是，于是我们要求的是以下4种情况 ``` 00101...0101...10100 00101...0101...01011 11010...0101...10100 11010...0101...01011 ``` 我们拿其中一种来做一下金字塔演变 ``` 00000010... 00000101... 00001010... 00010101... 00101010... ``` 同样地，如果有一侧是1，那上边就越来越多的1，也就是说，塔尖靠近哪个端点，最后就会成为那个端点的值（距离相等的时候两端点必然会是同0或同1），也就是说，我们可以以$O(n)$的复杂度判断塔尖是0还是1。 于是加上二分m，我们便可以以$O(nlogn)$的复杂度算出塔尖上的数字了。