【MySQL】滑动窗口函数详解

1️⃣什么是滑动窗口

首先，分享一道leetcode题，滑动窗口最大值

问题描述：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例：

输入：[2，3，4，2，6，2，5，1]，3

输出：[4，4，6，6，6，5]

分析问题:

这道题的关键点在于求滑动窗口中的最大值。大小为k的滑动窗口，我们可以通过遍历的方式来求出其中的最大值，需要O(k)的时间复杂度。对于大小为n的数组nums，一共有n-k+1个窗口，因此该算法的时间复杂度是O(nk)。

通过观察，我们可以知道，对于两个相邻的滑动窗口，有k-1个元素是共用的，只有一个元素是变化的，因此我们可以利用此性质来优化我们的算法。

解题思路：

设窗口区间为 [i,j] ，最大值为 $x_j$ 。当窗口向前移动一格，则区间变为[i+1,j+1]，即添加了nums[j+1] ，删除了 nums[i] 。

若只向窗口 [i,j] 右边添加数字 nums[j+1] ，则新窗口最大值可以 通过一次对比使用$O(1)$ 时间得到，即：

$$x_{j+1}=max(x_j,nums[j+1])$$

而由于删除的 nums[i] 可能恰好是窗口内唯一的最大值 $x_j$ ，因此不能通过以上方法计算$x_{j+1}$，而必须使用 $O(j-i)$时间， 遍历整个窗口区间获取最大值，即：

$$x_{j+1}=max(nums(i+1),\cdots ,num(j+1))$$

根据以上分析，可得 暴力法 的时间复杂度为 $O((n-k+1)k)\approx O(nk)$ 。

• 设数组 nums 的长度为n ，则共有 (n−k+1) 个窗口；
• 获取每个窗口最大值需线性遍历，时间复杂度为 $O(k)$ 。

本题难点： 如何在每次窗口滑动后，将 “获取窗口内最大值” 的时间复杂度从 O(k) 降低至 O(1) 。

使用 单调栈 实现了随意入栈、出栈情况下的 $O(1)$时间获取 “栈内最小值” 。本题同理，不同点在于 “出栈操作” 删除的是 “列表尾部元素” ，而 “窗口滑动” 删除的是 “列表首部元素” 。

窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决以上问题。遍历数组时，每轮保证单调队列 $deque$ ：

1. $deque$ 内 仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 nums[i−1] ，需将 $deque$ 内的对应元素一起删除。
2. $deque$ 内的元素 非严格递减 ⇒ 每轮窗口滑动添加了元素 nums[j+1] ，需将 $deque$ 内所有 <nums[j+1] 的元素删除。

算法流程：

1. 初始化： 双端队列 $deque$，结果列表 $res$ ，数组长度$n$ ；
2. 滑动窗口： 左边界范围 $i\in [1-k,n-k]$ ，右边界范围$j\in [0,n-1]$；
   1. 若 $i>0$ 且 队首元素 $deque[0]=$ 被删除元素 $nums[i-1]$ ：则队首元素出队；
   2. 删除 $deque$ 内所有 $<nums[j]$ 的元素，以保持 $deque$ 递减；
   3. 将 $nums[j]$ 添加至 $deque$ 尾部；
   4. 若已形成窗口（即 $i\ge 0$ ）：将窗口最大值（即队首元素 $deque[0]$ ）添加至列表 $res$ ；
3. 返回值： 返回结果列表 $res$ ；

Java代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0 || k <= 0) {
        return new int[0];
    }
    Deque<Integer> deque = new LinkedList<>();
    int[] res = new int[nums.length - k + 1];
    for (int j = 0, i = 1 - k; j < nums.length; j++, i++) {
        // 删除deque中对应的nums[i-1]
        if (i > 0 && deque.peekFirst() == nums[i - 1]) {
            deque.removeFirst();
        }
        //保持 deque递减
        while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
            deque.removeLast();
        }
        deque.addLast(nums[j]);
        //记录窗口最大值
        if (i >= 0) {
            res[i] = deque.peekFirst();
        }
    }

    return res;
}

2️⃣ MySQL中的滑动窗口函数

滑动窗口函数需要MySQL版本在8.x以上

创建sql表和插入数据

CREATE TABLE employeesalary (
    Id BIGINT NOT NULL,
    Name VARCHAR(255) NOT NULL,
    Salary FLOAT NOT NULL,
    DepartmentId INT NOT NULL,
    PRIMARY KEY (Id)
);


INSERT INTO employeesalary (id, Name, Salary, DepartmentId) VALUES
(1, 'Joe', 85000.00, 1),
(4, 'Max', 69000.00, 1),
(5, 'Janet', 69000.00, 1),
(6, 'Randy', 85000.00, 1),
(7, 'Will', 70000.00, 1),
(2, 'Henry', 80000.00, 2),
(3, 'Same', 60000.00, 2);

语法介绍

窗口函数语法：

<窗口函数> over (partition by <用于分组的列名>
order by <用于排序的列名>
rows/range子句<用于定义窗口大小> )

<窗口函数>可以放以下两种函数：
1） 专用窗口函数，包括后面要讲到的rank, dense_rank, row_number等专用窗口函数。
2） 聚合函数，如sum. avg, count, max, min等

1）专用窗口函数

简略说就是：

• Rank：有相同名次，名次按实际个数走，会跳数字。
• Dense_rank: 有相同名次，名次不跳数
• Row_number：相同分数按行数排序

分数	Rank	Dense_Rank	Row_number
100	1	1	1
100	1	1	2
90	3	2	3

2）聚合函数

这里以sum()为例子，使用常用的部门员工数据集，介绍聚合函数的不同组合用法

例1： 求各个部门的薪酬总数：

3） 滑动窗口：rows&range用法

[<ROWS or RANGE clause> BETWEEN <Start expr> AND <End expr>]

• ROWS: 表示按照行的范围进行定义框架，根据order by子句排序后，取的前N行及后N行的数据计算（与当前行的值无关，只与排序后的行号相关）。常用：rows n perceding表示从当前行到前n行（一共n+1行）

• **RANGE：**表示按照值的范围进行定义框架，根据order by子句排序后，指定当前行对应值的范围取值，行数不固定，只要行值在范围内，对应行都包含在内。适用于对日期、时间、数值排序分组

边界可取值（Start expr & End expr）	说明
Current Row	当前行
N preceding	前 n 行，n 为数字， 比如 2 Preceding 表示前2行
unbounded preceding	开头
N following	后N行，n 为数字， 比如 2 following 表示后2行
unbounded following	结尾

range取特定日期区间	说明
range interval 7-1 day preceding	最近7天的值
range between interval 1 day preceding and interval 1 day following	前后一天和当天的值

例2：求按id号累计员工的薪资（rows 用法）

注：如果将这里的rows 换成range 结果是一样的，因为这里使用id号排序，id和行号一致。

例3：求每个员工的薪资情况以及对应±1万元及±5千元薪资范围内的人数 （Range用法）

Range 是根据值来组合排序的，结果中的第一行 Same的工资是60000， 而薪资范围内在50000-70000的人一共有4个，薪资范围内在55000-65000的人只有一个。

原文地址：https://blog.csdn.net/weixin_45683778/article/details/142977258

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！