c*****e
发帖数: 67 | 1 直接二分：
left和right先skip掉相同的数，
然后left, right取mid，看mid的左[mid-1]右[mid+1]：
如果左右都小，则找到；
如果左小右大，则在非递减部分，更新left=mid+1
如果左大右小，则在非递增部分，更新right=mid-1
贴个js代码不知道有没有bug，有的话麻烦提一下：
function turnPoint(a) {
var left = 0,
right = a.length - 1,
mid,
len = a.length;
while (left <= right) {
while (left <= right && a[left + 1] == a[left]) left++;
while (left <= right && a[right - 1] == a[right]) right--;
mid = (left + right) / 2;
if (mid > 0 && mid + 1 < l... 阅读全帖 |
|
n****e
发帖数: 678 | 2 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
n****e
发帖数: 678 | 3 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
w*******e
发帖数: 395 | 4 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
” |
|
w*******e
发帖数: 395 | 5 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
” |
|
m**********e
发帖数: 1045 | 6 I think its turnpoint of japan
from prosperity to decadence
mark my words |
|
|
|
t**u
发帖数: 1572 | 9 It is impossible to predict 100% correctly. Can the volume and price be used
to predict turnpoint? For example, yesterday and today, there were large
volume at the last 30 minutes. Qiuyueshifu can also make some prediction
based on temperature ( a word I don't understand).
one can be right at every turing point, becasue predicting turning point is
much more difficult than predicting trend). |
|
