请教算法：从一维数组中找到足够宽度的波峰

runnerchin

遇事不决问外野。请教各位一个算法问题，琢磨了两天没琢磨出结果：
一个数组包含200个数字，如何找到一个合适的【合格值】，使得数组中可以找到一个平均值最大的连续合格的区段（区段长度介于25~40）。
或者另一个版本，如何找到这段数组中的最高（值最大）的连续突起区段（区段长度介于25~40），不足25宽度的区段略过，超过40的区段截取前40个元素。不知道大家有没有思路。在此先行谢过。

nuclearg

没细想，看上去和接雨水一模一样，找个正在背八股文的本科生应该十分钟就能把代码给你默写出来

假侦探trap

200个数字直接暴力搜索吧，别整高级的了

无糖百事可乐

语文问题
当你把问题表述清楚，网友能看懂的时候，问题也就迎刃而解了




原题：一个数组包含200个数字，如何找到一个合适的【合格值】，使得数组中可以找到一个平均值最大的连续合格的区段（区段长度介于25~40）。







首先定义下“合格”，你没说清楚，我先假设数值大于“合格值”为合格。
有了合格值后就可以判断数组中每个数值是否“合格”，并记录连续合格Combo数。这个应该不难。就是曲线下面那几个横线，找出最长的一条。
合格值可以从数组中最小值开始，那么每个数都合格200Combo。慢慢把合格值往上提，直到Combo数减少至25。【暴论：Combo数等于25时合格值最大，不用考虑25~40的范围】

ryanz

编辑，题意理解错误

tsubasa9

滑动窗口不就行了？

Hydro

蛤？
这不就是从极大值向下检测，检测到第一处满足长度在25-40的区间就行了吗
可能能根据某个数据结构存储，极大值m1后，次大值m2，次次大值m3出现的位置以及能不能连成区间
或是以位置看，连成区间的数字能不能满足在当前检测的基准线上
说不定有数据结构，但是才200个数字？不是性能要求非常高的话随便scan几下就出来了吧

runnerchin

我先试试逐段求和。谢谢各位指点。

流缨

一开始还没太看明白，A股收盘推送了想起来了，这不就是求MACD吗？构造函数吧

马猴肥宅

Hydro 发表于 2024-7-12 16:11
蛤？
这不就是从极大值向下检测，检测到第一处满足长度在25-40的区间就行了吗
可能能根据某个数据结构存储 ...

不一定连续所以不行吧

哌啶

为啥不用cursor

Hydro

马猴肥宅 发表于 2024-7-12 16:25
不一定连续所以不行吧

第二行，区间，我指的是index连续的
1、按照value排序，并记录原始index位置
2、从第25个value（因为连满足条件的数连25个都没有则肯定不会有那种index连续25次的区间），拓展，26th 27th... 直到发现有一个index连续，长达25次（这种方式发现的第一个长度25区间一定是平均值最大）
3、就是这个value

七把钥匙

问一下chatgpt吧

Hydro

量定了的话，才200个，连大O表示法都省了，直接跑benchmark把
要是一次性程序就更简单了，值之间相差不大直接从极大值步进向下扫，排序都不用，或是绘图然后瞪眼法蒙一个也行，反正这种情况算法不重要结果才重要

gammatau

Hydro 发表于 2024-7-12 16:11
蛤？
这不就是从极大值向下检测，检测到第一处满足长度在25-40的区间就行了吗
可能能根据某个数据结构存储 ...

不对吧，平均值最大的区间完全可以不包括前K个最大值的

ZekNagPul

滑窗检测就行，我们来问一下gpt

import tkinter as tk
from tkinter import filedialog
import pandas as pd
import numpy as np

def select_file():
    root = tk.Tk()
    root.withdraw()
    file_path = filedialog.askopenfilename(filetypes=[("Excel files", "*.xlsx;*.xls")])
    return file_path

def find_optimal_segment(data, min_length=25, max_length=40):
    n = len(data)
    best_avg = float('-inf')
    best_start = 0
    best_end = 0
    best_threshold = 0

    for threshold in sorted(set(data)):
        qualified = (data >= threshold).astype(int)
        cumsum = np.cumsum(qualified * data)
        cumcount = np.cumsum(qualified)

        for i in range(n):
            for j in range(i + min_length - 1, min(i + max_length, n)):
                if j - i + 1 < min_length:
                    continue
                if cumcount[j] - (cumcount[i-1] if i > 0 else 0) == j - i + 1:
                    avg = (cumsum[j] - (cumsum[i-1] if i > 0 else 0)) / (j - i + 1)
                    if avg > best_avg:
                        best_avg = avg
                        best_start = i
                        best_end = j
                        best_threshold = threshold

    return best_threshold, best_start, best_end, best_avg

# 主程序
file_path = select_file()
if file_path:
    # 读取Excel文件
    df = pd.read_excel(file_path)
   
    # 假设数据在第一列
    data = df.iloc[:, 0].values
   
    threshold, start, end, avg = find_optimal_segment(data)
   
    print(f"最佳合格值: {threshold}")
    print(f"最佳区段: 从索引 {start} 到 {end}")
    print(f"区段长度: {end - start + 1}")
    print(f"平均值: {avg}")
else:
    print("没有选择文件")


这个脚本做了以下几件事：

使用tkinter创建一个文件选择对话框，让用户选择Excel文件。

使用pandas读取选中的Excel文件。

定义了一个find_optimal_segment函数，该函数会遍历所有可能的阈值（合格值）和区段，找到满足条件的最佳区段。

在主程序中，我们调用这个函数并打印结果。

使用说明：

运行脚本后，会弹出一个文件选择对话框。

选择你的Excel文件。

脚本会处理Excel文件的第一列数据。如果你的数据在其他列，你需要修改df.iloc[:, 0]中的0为appropriate合适的列索引。

脚本会输出最佳合格值、最佳区段的起始和结束索引、区段长度和平均值。

注意：这个算法的时间复杂度是O(n^3)，其中n是数据的长度。如果你的数据量很大，可能需要较长的处理时间。对于大型数据集，可能需要考虑更加优化的算法。

Hydro

gammatau 发表于 2024-7-12 16:47
不对吧，平均值最大的区间完全可以不包括前K个最大值的

看12楼？或是想象用水平的塑料片，""从上到下""削一座冰沙山
第一个使得出现横向长度25的冰沙坨坨的塑料片高度即为所求，从上到下一定是从极大值开始（因为再高没有意义），但第一个横向长度25的冰沙坨坨不一定包含极大值
还是说我搞错了什么东西？

Hydro

嗯？如果可以断言，某给定一个合格阈值，如果存在，则最后结果的冰沙坨坨长度如果存在则长度一定是25（假设没有同大的平均值但长度是26 27的）
那我不是直接固定25长度开滑吗，25个数字和最大的即为所求，合格阈值是25个数字里最小的那个
对...对吗？

runnerchin

我最初想的也是从最高值向最低值削峰，不过遍历次数完全看脸。这个数据需要实时处理，大概在250条/秒。

gammatau

Hydro 发表于 2024-7-12 16:11
蛤？
这不就是从极大值向下检测，检测到第一处满足长度在25-40的区间就行了吗
可能能根据某个数据结构存储 ...

平均值不一定包含极大值点，最糟情况你得从第1 2 3 一直找到第n/2个极大值点才是最大平均值区间 不过这个方法碰到已扫过的区间就中断应该可以很直观地做成O(n)

转念一想，也许这个问题有信号处理学上的解法，直接FFT

Wiksy

Hydro 发表于 2024-7-12 16:58
嗯？如果可以断言，某给定一个合格阈值，如果存在，则最后结果的冰沙坨坨长度如果存在则长度一定是25（假设 ...

不行，简单的反例：
1 （24个0） 1

合格区间是全26个（均值1/13），只取25个只能得到1/25

Hydro

Wiksy 发表于 2024-7-12 17:26
不行，简单的反例：
1 （24个0） 1

对，削峰法的结束条件是找到连续25次的index，但不一定只连续25次，一次下降导致两个区间连起来的情况区间长度增值就不是1，不能推出最终长度是25

单流灯塔

参考力扣644:子数组最大平均数，用二分法的时间复杂度是nlogm，m是数组最大值和最小值的差。

目测楼主的问题只需要在判断时加上最大长度限制，再加上最小值限制就好了。

不过考虑到数据大小，可能计算前缀和然后计算所有长度为25~40的子区间的均值更快吧。。。

—— 来自 Xiaomi 23113RKC6C, Android 14上的 S1Next-鹅版 v3.0.0.81-alpha

单流灯塔

单流灯塔 发表于 2024-7-12 17:36
参考力扣644:子数组最大平均数，用二分法的时间复杂度是nlogm，m是数组最大值和最小值的差。

目测楼主的问 ...

哦看错题了。。。如果求合格值更简单了，先求均值最大的子区间，子区间最小值就是合格值

—— 来自 Xiaomi 23113RKC6C, Android 14上的 S1Next-鹅版 v3.0.0.81-alpha

Hydro

单流灯塔 发表于 2024-7-12 17:36
参考力扣644:子数组最大平均数，用二分法的时间复杂度是nlogm，m是数组最大值和最小值的差。

目测楼主的问 ...

正确的
如何找到一个合适的【合格值】，使得数组中可以找到一个平均值最大的连续合格的区段（区段长度介于25~40）✖
数组中平均值最大的连续区间是什么（合格值肯定是它的最小值）✔

另外，24楼"nlogm，m是极差"，这也是削峰，但是二分？

单流灯塔

Hydro 发表于 2024-7-12 18:03
正确的
如何找到一个合适的【合格值】，使得数组中可以找到一个平均值最大的连续合格的区段（区段长度介 ...

没错，因为均值的取值在最小值和最大值之间，因此与其从最大值一点一点往下试，不如用二分法试

—— 来自 Xiaomi 23113RKC6C, Android 14上的 S1Next-鹅版 v3.0.0.81-alpha

巨魔已被忠诚

滑动平均滤波
或者说是滑动窗口均值滤波，要求窗口大小可调

mimighost

25-40 直接扫就行了

甚至你都可以说这个复杂度已经是线性的了

VMDL

姑且假设楼主的题意如下：

给定长为 n (1 <= n <= 200) 的数组 a，求平均值最大的，长度介于 25 到 40 的区间，且在这个基础上使得区间的最小值（即合格值）最大。

这个可以用二分 + 单调队列解决：

1. 首先二分最大的平均值，做法是二分平均值 w，再构造一个新数组 b，使得每个数都是 a-w，接下来计算新数组 b 的前缀和，同时按照如下方式维护单调队列：

  i.  如果队首不符合区间长度限制，那么弹出队首；
  ii. 计长度为 25 的区间对应的前缀和为 x，那么弹出所有值大于 x 的队尾，然后插入 x。

如果操作后的队尾对应前缀和不大于当前前缀和，即说明存在对应平均值的区间。

2. 在求出平均数的基础上二分合格值，按照上述方法记录单调队列，但遇到不合格值则清空队列。

这样是 n*log值域 的，虽然在这个数据范围下不一定比直接扫更快。

orecheng

https://www.cnblogs.com/bonne-chance/p/17413412.html
能用工具箱，干嘛要自己写
python的scipy.signal.find_peaks

1. import numpy as np
   
2. from scipy.signal import find_peaks
   
3. import matplotlib.pyplot as plt
   
4. 
   
5. def find_max_average_segment(arr, min_width=25, max_width=40, min_height_ratio=0.5):#区段最小值不得小于最大值的50%
   
6.     # 寻找峰值
   
7.     peaks, _ = find_peaks(arr, distance=min_width, width=[min_width, max_width])
   
8.    
   
9.     # 初始化最大平均值的区段信息
   
10.     max_avg = -np.inf
    
11.     max_segment = (None, None)
    
12.    
    
13.     # 遍历每个峰，找到符合条件的区段
    
14.     for peak in peaks:
    
15.         # 确定区段的左右边界
    
16.         left = max(0, peak - max_width // 2)
    
17.         right = min(len(arr), peak + max_width // 2)
    
18.         
    
19.         # 确保区段至少为min_width宽度
    
20.         if right - left < min_width:
    
21.             continue
    
22.         
    
23.         # 截取长度为max_width的区段
    
24.         segment = arr[left:right]
    
25.         
    
26.         # 计算区段平均值
    
27.         segment_avg = np.mean(segment)
    
28.         
    
29.         # 检查区段的最小值是否满足条件
    
30.         if np.min(segment) >= min_height_ratio * arr[peak]:
    
31.             # 更新最大平均值区段
    
32.             if segment_avg > max_avg:
    
33.                 max_avg = segment_avg
    
34.                 max_segment = (left, right)
    
35.    
    
36.     return max_segment
    
37. 
    
38. def plot_selected_segments(arr, segments):
    
39.     plt.figure(figsize=(12, 6))
    
40.     plt.plot(arr, label='Array data')
    
41.    
    
42.     # 标记选中的区段
    
43.     for left, right in segments:
    
44.         plt.plot(range(left, right), arr[left:right], 'o', label=f'Segment {left}-{right}')
    
45.    
    
46.     plt.legend()
    
47.     plt.show()
    
48. 
    
49. # 示例数组和参数
    
50. np.random.seed(1)
    
51. example_array = np.random.randn(500).cumsum()
    
52. min_width = 25
    
53. max_width = 40
    
54. min_height_ratio = 0.5
    
55. 
    
56. # 找到最大平均值区段
    
57. segment = find_max_average_segment(example_array, min_width, max_width, min_height_ratio)
    
58. 
    
59. # 如果找到了区段，则绘制图像
    
60. if segment[0] is not None and segment[1] is not None:
    
61.     plot_selected_segments(example_array, [segment])
    
62. else:
    
63.     print("没有找到符合条件的区段。")
    

复制代码

yeo

cumsum错位想减取top1

如果要求凸起，那就以凹点把序列切割成子序列。凹点含义是左右两边的点都严格大于它

哦，找到所有的突点然后扩张这些凸点貌似效率更高

runnerchin

多谢各位指教，受益匪浅。我挨个试试看。