还想O(n)搞一遍的统统拉出去枪毙。

直觉上一定是二分,那么单调性体现在哪里?

不妨先考虑下这个序列的特征:a1 ... ak-1 ak ak+1 ... an,如果ak是序列rotate前的第一个数字,那么ak < ak+1 < ... < an < a1 ... < ak-1,很显然,问题的解就是ak。初始化l = 1, r = n, 那么当前mid = (l + r) / 2位置的数字如果比现在已知的最小数字Min(初始化Min = ar = an)小的话,那么答案至少在包括mid位置的左面,此时更新Min,否则答案在mid右面。