如何查找数组的局部峰值点

具体说就是 给出所有这样的点:它在其前后各k个点中最大

看起来很像leetcode里的题目吧  其实想问的是 如何获取股票的阶段高位

这个是不是线性时间有解 抑或有更快的?

好奇这些常见的需求 是不是有人写好现成的函数可以用啊 搜了下 好像matlab里 findpeaks函数就是做这个的 那pandas里有啥对应的玩意吗


网友评论:
线性时间当然是有解的,再低当然是无解的- -

—— 来自 Meizu 16th, Android 8.1.0上的 v2.0.3-play
只要你的前后各K个这个K是一个固定的不大的数字。
那么O(2kn)=O(n)
用单调栈可以线性求出,对于某个元素,以它为最小值的区间
感觉可以堆排序,理想状态下NlogK
可以做堆优化,维护一个容量限制为2k的堆,每次滑动窗口进行插入删除操作,堆顶元素一直就是周围2k范围内最大的数。这样时间复杂度只有O(n*logk)。
不固定的范围查询应该可以用线段树吧


我理解你的需求应该是 time series change point detection

因为真实世界的时间序列(比如交易数据)非常复杂, 波动很剧烈, 有一个整体和局部的问题, 用单调栈来解决那几乎所有的点都是突变点了. 都是跟 leetcode 上的题完全不是一个层次的问题

算法很多, 实现大部分都是拿 matlab 或者 r 写的玩具


http://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.find_peaks.html
这个就是参考matlab弄的

http://github.com/scipy/scipy/issues/8211

发自我的iPhone via Saralin 2.1.4

来自: iPhone客户端
单调队列做两次

嗯 是我问题描述的不准确 阶段高位不是local peak那么简单 还有趋势什么的
网上搜到的解释



这个东西这么复杂啊 又是贝叶斯 谱密度 还要多次回归啥啥的
统计门外汉还是不研究算法咋实现的了(感觉我面临最大的困难是 搜都不知道按什么关键字搜索。。。 )

标签:    发布日期:06-24