$1.50 Skintimate Cream Shave Coupon!# PennySaver - 省钱一族
a*e
1 楼
log（n）的要求一下想到binary search，但总觉得这个题很怪，有任何实际应用吗？
https://oj.leetcode.com/discuss/18107/o-logn-solution-javacode
看到这个讨论，知道如果推出这一步，就好做了，但怎么能够推到这一步？特别是
•If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a
peak
•If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a
peak
继续想。。。。。。。。。。。
This problem is similar to Local Minimum. And according to the given
condition, num[i] != num[i+1], there must exist a O(logN) solution. So we
use binary search for this problem.
•If num[i-1] < num[i] > num[i+1], then num[i] is peak
•If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a
peak
•If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a
peak
•If num[i-1] > num[i] < num[i+1], then both sides have peak (n is num.
length)
https://oj.leetcode.com/discuss/18107/o-logn-solution-javacode
看到这个讨论，知道如果推出这一步，就好做了，但怎么能够推到这一步？特别是
•If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a
peak
•If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a
peak
继续想。。。。。。。。。。。
This problem is similar to Local Minimum. And according to the given
condition, num[i] != num[i+1], there must exist a O(logN) solution. So we
use binary search for this problem.
•If num[i-1] < num[i] > num[i+1], then num[i] is peak
•If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a
peak
•If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a
peak
•If num[i-1] > num[i] < num[i+1], then both sides have peak (n is num.
length)