算法思路

1. 均值 & 标准差

   • 用前缀和与前缀平方和可快速计算：

     • sum = prefix[i+w] - prefix[i]
     • mean = sum / w
     • var = (Σy² - w*mean²) / (w-1)
     • std = sqrt(max(var,0))

2. 最小值 & 最大值

   • 简单做法：每个窗口遍历一遍 O(w)。
   • 高效做法：用单调队列，O(n) 解决所有窗口的 min/max。

3. 斜率 slope

   • 公式：

     slope = (w * Σ(x*y) - Σx * Σy) / (w * Σx² - (Σx)²)
     

     其中 x = 0..w-1，Σx 和 Σx² 可直接公式计算。

   • 特殊情况：w=1 时，分母为 0，slope=0。

4. 对齐方式

   • 输出行数 n = len(a) - max(wins) + 1。
   • 对于窗口大小 w，第 r 行的数据对应起点 idx = r + (Wmax - w)。

复杂度分析

• 朴素实现：每个窗口 O(w)，总复杂度 O(N * Σw)。
• 优化实现：前缀和+单调队列+公式，复杂度 O(N * |wins|)。
• 空间复杂度 O(N)。

代码实现

Python

import sys, re
import numpy as np
from numpy.lib.stride_tricks import sliding_window_view


txt = eval(sys.stdin.read())

a = np.array(txt[0], dtype=float)
wins = np.array(txt[1], dtype=int)

if a.size == 0 or wins.size == 0:
    print("[]"); sys.exit(0)

Wmax = int(wins.max())
n = a.size - Wmax + 1
if n <= 0:
    print("[]"); sys.exit(0)

# —— 工具：数值格式化（最多3位小数，去掉多余0和小数点） ——
def fmt_arr(x: np.ndarray):
    y = np.round(x, 3)                                 # 四舍五入到3位
    s = np.char.mod('%.3f', y)                         # 统一三位
    s = np.char.rstrip(np.char.rstrip(s, '0'), '.')    # 去尾0与点
    s = np.where(s == '', '0', s)                      # 处理 -0 -> 0
    return s.tolist()

# —— 主逻辑：对每个 w 计算整批窗口特征（均值/标准差/最小/最大/斜率） ——
# 斜率：对 x=0..w-1，用中心化公式 beta = sum((x-x̄)*(y-ȳ)) / sum((x-x̄)^2)
features_per_w = {}  # w -> (mean, std, min, max, slope), 每个都是 shape=(N-w+1,)
N = a.size

for w in wins:
    W = sliding_window_view(a, w)            # 形状: (N-w+1, w)
    mean = W.mean(axis=1)
    # 样本标准差 ddof=1；w=1 时结果为 nan，按题意置 0
    std = W.std(axis=1, ddof=1)
    std = np.nan_to_num(std, nan=0.0)

    mn = W.min(axis=1)
    mx = W.max(axis=1)

    x = np.arange(w, dtype=float)
    xc = x - x.mean()                         # x 中心化
    denom = np.sum(xc * xc)                   # 标准化分母
    # 将每个窗口的 y 做中心化，再与 xc 点积即可得到所有斜率
    yc = W - mean[:, None]
    slope = yc @ xc / (denom if denom != 0 else 1.0)
    if denom == 0: slope[:] = 0.0            # w=1 的情况

    features_per_w[int(w)] = (mean, std, mn, mx, slope)

# —— 对齐规则：第 r 行使用每个 w 的索引 r + (Wmax - w) ——
rows = []
for r in range(n):
    parts = []
    for w in wins:
        idx = r + (Wmax - int(w))
        mean, std, mn, mx, slope = features_per_w[int(w)]
        parts.extend(fmt_arr(np.array([mean[idx], std[idx], mn[idx], mx[idx], slope[idx]])))
    rows.append("[" + ", ".join(parts) + "]")

print("\n".join(rows))

Java

import java.util.*;

public class Main {
    // 提取字符串中的整数，返回 int 数组
    static int[] parse(String s) {
        ArrayList<Integer> v = new ArrayList<>();
        // 把非数字和负号替换成空格，方便 Scanner 读取
        Scanner sc = new Scanner(s.replaceAll("[^0-9\\-]", " "));
        while (sc.hasNextInt()) v.add(sc.nextInt()); // 逐个读出整数
        sc.close();
        int[] arr = new int[v.size()];
        for (int i=0;i<arr.length;i++) arr[i]=v.get(i); // 转换为数组
        return arr;
    }

    // 数值格式化：最多保留 3 位小数，去掉多余 0 和小数点
    static String fmt(double x) {
        double y = Math.round(x * 1000.0) / 1000.0;              // 四舍五入到三位
        String s = String.format(Locale.US, "%.3f", y);          // 格式化为三位小数
        int p=s.length()-1;
        while (p>=0 && s.charAt(p)=='0') p--;                    // 去掉末尾的 0
        if (p>=0 && s.charAt(p)=='.') p--;                       // 去掉末尾的小数点
        return p>=0? s.substring(0,p+1):"0";                     // 防止结果为空
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if (!in.hasNextLine()) return;           // 没有输入直接退出
        String line = in.nextLine();             // 读入一行
        in.close();

        // 查找分隔符 "], ["
        int pos=line.indexOf("], [");
        if (pos==-1) { System.out.println("[]"); return; }

        // 切分为两个子串：s1 表示原数组，s2 表示窗口数组
        String s1=line.substring(0,pos+1);
        String s2=line.substring(pos+1);

        int[] a=parse(s1);       // 原数组
        int[] wins=parse(s2);    // 窗口大小数组
        if (a.length==0 || wins.length==0) { System.out.println("[]"); return; }

        // 找出最大窗口，计算行数
        int Wmax=Arrays.stream(wins).max().getAsInt();
        int n=a.length - Wmax + 1;
        if (n<=0) { System.out.println("[]"); return; }

        StringBuilder out=new StringBuilder();
        // 遍历每一行（输出 n 行）
        for (int r=0;r<n;r++) {
            ArrayList<String> row=new ArrayList<>();
            // 遍历每个窗口大小
            for (int w: wins) {
                int s=r+(Wmax-w);    // 当前窗口的起点索引

                // 均值 / 最小值 / 最大值
                double sum=0; int mn=Integer.MAX_VALUE,mx=Integer.MIN_VALUE;
                for (int k=0;k<w;k++) {
                    int v=a[s+k];
                    sum+=v; mn=Math.min(mn,v); mx=Math.max(mx,v);
                }
                double mean=sum/w;

                // 样本标准差（ddof=1）
                double stdv=0;
                if (w>1) {
                    double sq=0;
                    for (int k=0;k<w;k++) {
                        double d=a[s+k]-mean; sq+=d*d;
                    }
                    stdv=Math.sqrt(sq/(w-1));
                }

                // 线性回归斜率（最小二乘）
                double sumx=0,sumx2=0,sumy=0,sumxy=0;
                for (int k=0;k<w;k++) {
                    sumx+=k; sumx2+=1.0*k*k;
                    sumy+=a[s+k]; sumxy+=1.0*k*a[s+k];
                }
                double D=w*sumx2 - sumx*sumx;
                double slope=(D==0?0:(w*sumxy - sumx*sumy)/D);

                // 将结果按要求加入当前行
                row.add(fmt(mean));
                row.add(fmt(stdv));
                row.add(Integer.toString(mn));
                row.add(Integer.toString(mx));
                row.add(fmt(slope));
            }
            // 拼接一行输出
            out.append('[').append(String.join(", ", row)).append(']');
            if (r+1<n) out.append('\n'); // 行间换行
        }
        System.out.print(out.toString()); // 最终输出
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 把字符串里的整数提取出来
vector<int> parse(const string& s) {
    vector<int> v; stringstream ss(s);
    char c;
    // 逐个读取字符
    while (ss >> c) {
        // 如果是数字或负号，就回退一格再读取成整数
        if ((c >= '0' && c <= '9') || c == '-') {
            ss.unget();          // 把字符放回流
            int x; ss >> x;      // 读取一个整数
            v.push_back(x);      // 保存到结果数组
        }
    }
    return v;
}

// 保留最多三位小数，去掉多余 0 和点
string fmt(double x) {
    double y = round(x * 1000.0) / 1000.0;   // 四舍五入到三位小数
    stringstream ss; 
    ss << fixed << setprecision(3) << y;     // 格式化成固定三位小数
    string s = ss.str();
    while (!s.empty() && s.back() == '0') s.pop_back(); // 去掉末尾的 0
    if (!s.empty() && s.back() == '.') s.pop_back();    // 去掉末尾的小数点
    if (s.empty()) s = "0";                // 防止为空
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line; getline(cin, line);          // 输入一行，如 [1,2,3,4,5],[2,3]
    auto pos = line.find(']');                // 找到第一个 ] 的位置
    string s1 = line.substr(0, pos+1);        // 前半部分（原数组）
    string s2 = line.substr(pos+1);           // 后半部分（窗口数组）

    vector<int> a = parse(s1);                // 解析原数组
    vector<int> wins = parse(s2);             // 解析窗口数组
    if (a.empty() || wins.empty()) {          // 边界处理
        cout << "[]\n"; 
        return 0; 
    }

    int Wmax = *max_element(wins.begin(), wins.end()); // 最大窗口大小
    int n = (int)a.size() - Wmax + 1;                  // 输出行数
    if (n <= 0) { cout << "[]\n"; return 0; }

    // 遍历每一行
    for (int r = 0; r < n; r++) {
        vector<string> row;    // 存储当前行的结果
        // 遍历每个窗口大小
        for (int w : wins) {
            int s = r + (Wmax - w);   // 当前窗口的起始下标

            // 计算均值 / 最小值 / 最大值
            double sum = 0; 
            int mn = INT_MAX, mx = INT_MIN;
            for (int k = 0; k < w; k++) {
                int v = a[s+k]; 
                sum += v;
                mn = min(mn, v); 
                mx = max(mx, v);
            }
            double mean = sum / w;

            // 计算样本标准差（ddof=1，w=1 时结果为 0）
            double stdv = 0;
            if (w > 1) {
                double sq = 0;
                for (int k = 0; k < w; k++) {
                    double d = a[s+k] - mean;
                    sq += d * d;
                }
                stdv = sqrt(sq / (w-1));
            }

            // 计算线性回归斜率
            double sumx=0,sumx2=0,sumy=0,sumxy=0;
            for (int k = 0; k < w; k++) {
                sumx += k; 
                sumx2 += 1.0*k*k;
                sumy += a[s+k]; 
                sumxy += 1.0*k*a[s+k];
            }
            double D = w*sumx2 - sumx*sumx;
            double slope = (D==0?0:(w*sumxy - sumx*sumy)/D);

            // 把结果存入当前行
            row.push_back(fmt(mean));
            row.push_back(fmt(stdv));
            row.push_back(to_string(mn));
            row.push_back(to_string(mx));
            row.push_back(fmt(slope));
        }

        // 输出当前行
        cout << '[';
        for (int i = 0; i < (int)row.size(); i++) {
            if (i) cout << ", ";   // 元素之间加逗号
            cout << row[i];
        }
        cout << "]";
        if (r+1<n) cout << "\n";   // 行与行之间换行
    }
    return 0;
}

题目内容

题目背景:

数据治理阶段经常会碰到特征转换，当前有一个时间序列数据(用 $1$ 维整数数组表示)，和一个窗口序列( $1$ 维整数数组)，窗口序列中每个元素表示 $1$ 个窗口 $w$ 。

转换要求:

实现一个多尺寸滑动窗口特征转换函数，每个窗口提取 $5$ 个特征，计算出来如果是整数不带小数点，则小数点后最多保留 $3$ 位(四舍五入)

小数点举例说明:

$1.0->1$ 整数不带小数点

$1.10->1.1$ 结尾不带 $0$

$1.1116->1.112$ 最多保留 $3$ 位小数，最后一位四舍五入

特征包含:

均值($mean$)

标准差(样本标准差，$ddof=1$ ;分母为 $0$ 时，返回 $0$ )

最小值($min$)

最大值($max$)

线性趋势斜率(使用线性回归拟合)

线性趋势斜率算法:

时间索引: $x = [0, 1, 2,...,w-1]$

对应的值: $y = [y_0,y_1, y_2,...,y_{w-1}]$

拟合一条直线:$y=βx+α$

$β$ 是斜率(我们需要的趋势斜率)

$α$ 是截距

使用最小二乘法，斜率的计算公式为:

$β = [n* ∑(xy) - ∑x*∑y] / [n*∑(x^2) - (∑x)^2]$

$n$ 是窗口大小

标准差计算公式:

$s=\sqrt{\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}}$

转换规则:

对于每个窗口大小 $w(window\_array$ 中的一个元素)，从索引(索引从 $0$ 开始)$i=max(window\_arravy)-w$ ，开始滑动窗口

所有窗口的特征按 $window\_arrav$ 中的元素顺序排列

如果数组长度小于任意一个窗口大小,则结果数组为空

输入描述

$input$_$array$ :一维数组,表示时间序列数据

$window$_$array$:一维数组,多个窗口，每个元素为窗口 $w$

输出描述

二维数组，形状为 $(n,m)$ ，其中:

$n = len(input\_array) - max(window\_array) +1$

$m = len(window\_array) * 5$

每一行说明:

$[mean1, std1, min1, max1, slope1, mean2, std2, min2, max2, slope2,...]$

样例1

输入

[10, 20], [3, 4]

输出

[]

说明

输入长度小于窗口最小大小，输出空数组

样例2

输入

[1, 2, 3, 4, 5], [2, 3]

输出

[2.5, 0.707, 2, 3, 1, 2, 1, 1, 3, 1]
[3.5, 0.707, 3, 4, 1, 3, 1, 2, 4, 1]
[4.5, 0.707, 4, 5, 1, 4, 1, 3, 5, 1]

说明

1、窗口大小 $2$ 的特征:

[2,3]: mean=2.5,std=0.707, min=2, max=3, slope=1

[3,4]: mean=3.5, std=0.707, min=3, max=4, slope=1

[4,5]: mean=4.5, std=0.707, min=4, max=5, slope=1

2、窗口大小 $3$ 的特征:

[1,2,3]: mean=2, std=1, min=1, max=3, slope=1

[2,3,4]: mean=3, std=1, min=2, max=4, slope=1

[3,4,5]: mean=4, std=1, min=3, max=5, slope=1