喜迎
春节

滑动窗口算法

PHP 算法 滑动窗口
算法
发布日期:   2024-11-13
文章字数:   821
阅读时长:   3 分

什么是滑动窗口算法？

滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。

应用场景

  • 字符串处理: 查找最长无重复子串、字符串的排列等。
  • 数组处理: 寻找数组中满足一定条件的子数组、滑动窗口的最大值/最小值等。
  • 数据流处理: 实时处理数据流，统计窗口内的统计量；进而进行下一步处理，如：限流(在一定时间窗口内限制请求的次数)、降权(如果十分钟的订单数超过100，且失败率高于40%，就把该充值渠道的优先级降到最低)等。

PHP实现滑动窗口算法

1. 基于数组实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 查找数组中滑动窗口内的最大值
 *
 * 整体思路是：
 *     1. 使用一个单调递减队列来存储索引，队列头部始终是当前窗口的最大值对应的索引。
 *     2. 每次循环，将当前元素与队列尾部的元素比较，如果当前元素更大，则将队列尾部的元素弹出，
 *          直到队列为空或当前元素小于等于队列尾部的元素。
 *     3. 当窗口滑动时，如果队列头部的索引对应的元素已经不在窗口内，则将其弹出。
 * @param $nums
 * @param $k
 * @return array
 */
function findMaxSlidingWindow($nums, $k): array
{
    $n = count($nums);&&
    if ($n == 0) {
        return [];
    }

    $q = []; // 单调递减队列，存储索引  队列头部始终是当前窗口的最大值对应的索引。
    $res = [];

    for ($i = 0; $i < $n; $i++) {
        // 保证队列中只保留索引对应的值大于等于nums[i]的元素
        while ($q && $nums[$q[count($q) - 1]] < $nums[$i]) {
            array_pop($q);
        }
        $q[] = $i;

        // 如果窗口已满，且窗口首元素已过期，则弹出
        if ($i >= $k - 1) {
            $res[] = $nums[$q[0]];      // 窗口最大值就是队列头部的元素
            if ($q[0] === $i - $k + 1) {    // 判断窗口左边界元素是否过期
                array_shift($q);
            }
        }
    }

    return $res;
}


// 调用
$nums = [2,5,3,4,5,2,6,3,2,4,10,1,2,0];
$res = $this->findMaxSlidingWindow($nums,3);
dump(json_encode($res));        // [5,5,5,5,6,6,6,4,10,10,10,2]

2. 基于双指针实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 查找最长无重复子串
 * @param $s
 * @return int|mixed
 */
function lengthOfLongestSubstring($s) {
    $n = strlen($s);
    $ans = 0;
    // 左右指针: 用两个指针left和right来表示滑动窗口的左右边界。
    $left = 0;
    $right = 0;
    $set = [];      // 哈希表: 用一个哈希表来记录窗口中出现的字符。
    while ($right < $n) {
        $c = $s[$right];
        // 窗口滑动: 当遇到重复字符时，左指针向右移动，直到窗口中不再包含重复字符。
        while (isset($set[$c])) {
            unset($set[$s[$left]]);
            $left++;
        }
        $set[$c] = true;
        $ans = max($ans, $right - $left + 1);
        $right++;
    }
    return $ans;
}

// 调用
$str = 'sdf233rdfekdfkkdfkdkgkdfgggegfgmffdfdfeer343ferrfe';
$res = $this->lengthOfLongestSubstring($str);
dump($res);        // 6

注意事项

  • 窗口大小: 滑动窗口的大小是根据具体问题来确定的。
  • 数据类型: 滑动窗口可以处理各种类型的数据，包括数字、字符等。
  • 时间复杂度: 滑动窗口算法的时间复杂度通常是O(n)，其中n是输入数据的长度。
文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/sliding-window.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 滑动窗口
赏
评 论
 本篇
滑动窗口算法
滑动窗口算法
什么是滑动窗口算法？滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。 应用场景 字符串处理: 查找最长无重复子串、字符串的排列等。 数组处理: 寻找数组中满足
2024-11-13 算法
PHP 算法 滑动窗口
下一篇 
PHP实现熔断机制
PHP实现熔断机制
什么是熔断机制？熔断机制是一种应对系统故障、防止级联故障的保护机制。当某个服务出现故障时，通过熔断机制，可以快速隔离故障服务，防止故障蔓延到整个系统，从而保证系统的稳定性。 熔断机制的核心要素 快速失败： 当服务不可用时，立即返回错误，防止
2024-11-13 系统设计
PHP 熔断
PHP 算法 滑动窗口
算法
发布日期:   2024-11-13
文章字数:   821
阅读时长:   3 分

什么是滑动窗口算法？

滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。

应用场景

  • 字符串处理: 查找最长无重复子串、字符串的排列等。
  • 数组处理: 寻找数组中满足一定条件的子数组、滑动窗口的最大值/最小值等。
  • 数据流处理: 实时处理数据流，统计窗口内的统计量；进而进行下一步处理，如：限流(在一定时间窗口内限制请求的次数)、降权(如果十分钟的订单数超过100，且失败率高于40%，就把该充值渠道的优先级降到最低)等。

PHP实现滑动窗口算法

1. 基于数组实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 查找数组中滑动窗口内的最大值
 *
 * 整体思路是：
 *     1. 使用一个单调递减队列来存储索引，队列头部始终是当前窗口的最大值对应的索引。
 *     2. 每次循环，将当前元素与队列尾部的元素比较，如果当前元素更大，则将队列尾部的元素弹出，
 *          直到队列为空或当前元素小于等于队列尾部的元素。
 *     3. 当窗口滑动时，如果队列头部的索引对应的元素已经不在窗口内，则将其弹出。
 * @param $nums
 * @param $k
 * @return array
 */
function findMaxSlidingWindow($nums, $k): array
{
    $n = count($nums);&&
    if ($n == 0) {
        return [];
    }

    $q = []; // 单调递减队列，存储索引  队列头部始终是当前窗口的最大值对应的索引。
    $res = [];

    for ($i = 0; $i < $n; $i++) {
        // 保证队列中只保留索引对应的值大于等于nums[i]的元素
        while ($q && $nums[$q[count($q) - 1]] < $nums[$i]) {
            array_pop($q);
        }
        $q[] = $i;

        // 如果窗口已满，且窗口首元素已过期，则弹出
        if ($i >= $k - 1) {
            $res[] = $nums[$q[0]];      // 窗口最大值就是队列头部的元素
            if ($q[0] === $i - $k + 1) {    // 判断窗口左边界元素是否过期
                array_shift($q);
            }
        }
    }

    return $res;
}


// 调用
$nums = [2,5,3,4,5,2,6,3,2,4,10,1,2,0];
$res = $this->findMaxSlidingWindow($nums,3);
dump(json_encode($res));        // [5,5,5,5,6,6,6,4,10,10,10,2]

2. 基于双指针实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 查找最长无重复子串
 * @param $s
 * @return int|mixed
 */
function lengthOfLongestSubstring($s) {
    $n = strlen($s);
    $ans = 0;
    // 左右指针: 用两个指针left和right来表示滑动窗口的左右边界。
    $left = 0;
    $right = 0;
    $set = [];      // 哈希表: 用一个哈希表来记录窗口中出现的字符。
    while ($right < $n) {
        $c = $s[$right];
        // 窗口滑动: 当遇到重复字符时，左指针向右移动，直到窗口中不再包含重复字符。
        while (isset($set[$c])) {
            unset($set[$s[$left]]);
            $left++;
        }
        $set[$c] = true;
        $ans = max($ans, $right - $left + 1);
        $right++;
    }
    return $ans;
}

// 调用
$str = 'sdf233rdfekdfkkdfkdkgkdfgggegfgmffdfdfeer343ferrfe';
$res = $this->lengthOfLongestSubstring($str);
dump($res);        // 6

注意事项

  • 窗口大小: 滑动窗口的大小是根据具体问题来确定的。
  • 数据类型: 滑动窗口可以处理各种类型的数据，包括数字、字符等。
  • 时间复杂度: 滑动窗口算法的时间复杂度通常是O(n)，其中n是输入数据的长度。
文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/sliding-window.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 滑动窗口
赏
评 论
 本篇
滑动窗口算法
滑动窗口算法
什么是滑动窗口算法？滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。 应用场景 字符串处理: 查找最长无重复子串、字符串的排列等。 数组处理: 寻找数组中满足
2024-11-13 算法
PHP 算法 滑动窗口
下一篇 
PHP实现熔断机制
PHP实现熔断机制
什么是熔断机制？熔断机制是一种应对系统故障、防止级联故障的保护机制。当某个服务出现故障时，通过熔断机制，可以快速隔离故障服务，防止故障蔓延到整个系统，从而保证系统的稳定性。 熔断机制的核心要素 快速失败： 当服务不可用时，立即返回错误，防止
2024-11-13 系统设计
PHP 熔断
PHP 算法 滑动窗口
算法
发布日期:   2024-11-13
文章字数:   821
阅读时长:   3 分

什么是滑动窗口算法？

滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。

应用场景

  • 字符串处理: 查找最长无重复子串、字符串的排列等。
  • 数组处理: 寻找数组中满足一定条件的子数组、滑动窗口的最大值/最小值等。
  • 数据流处理: 实时处理数据流，统计窗口内的统计量；进而进行下一步处理，如：限流(在一定时间窗口内限制请求的次数)、降权(如果十分钟的订单数超过100，且失败率高于40%，就把该充值渠道的优先级降到最低)等。

PHP实现滑动窗口算法

1. 基于数组实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 查找数组中滑动窗口内的最大值
 *
 * 整体思路是：
 *     1. 使用一个单调递减队列来存储索引，队列头部始终是当前窗口的最大值对应的索引。
 *     2. 每次循环，将当前元素与队列尾部的元素比较，如果当前元素更大，则将队列尾部的元素弹出，
 *          直到队列为空或当前元素小于等于队列尾部的元素。
 *     3. 当窗口滑动时，如果队列头部的索引对应的元素已经不在窗口内，则将其弹出。
 * @param $nums
 * @param $k
 * @return array
 */
function findMaxSlidingWindow($nums, $k): array
{
    $n = count($nums);&&
    if ($n == 0) {
        return [];
    }

    $q = []; // 单调递减队列，存储索引  队列头部始终是当前窗口的最大值对应的索引。
    $res = [];

    for ($i = 0; $i < $n; $i++) {
        // 保证队列中只保留索引对应的值大于等于nums[i]的元素
        while ($q && $nums[$q[count($q) - 1]] < $nums[$i]) {
            array_pop($q);
        }
        $q[] = $i;

        // 如果窗口已满，且窗口首元素已过期，则弹出
        if ($i >= $k - 1) {
            $res[] = $nums[$q[0]];      // 窗口最大值就是队列头部的元素
            if ($q[0] === $i - $k + 1) {    // 判断窗口左边界元素是否过期
                array_shift($q);
            }
        }
    }

    return $res;
}


// 调用
$nums = [2,5,3,4,5,2,6,3,2,4,10,1,2,0];
$res = $this->findMaxSlidingWindow($nums,3);
dump(json_encode($res));        // [5,5,5,5,6,6,6,4,10,10,10,2]

2. 基于双指针实现的滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 查找最长无重复子串
 * @param $s
 * @return int|mixed
 */
function lengthOfLongestSubstring($s) {
    $n = strlen($s);
    $ans = 0;
    // 左右指针: 用两个指针left和right来表示滑动窗口的左右边界。
    $left = 0;
    $right = 0;
    $set = [];      // 哈希表: 用一个哈希表来记录窗口中出现的字符。
    while ($right < $n) {
        $c = $s[$right];
        // 窗口滑动: 当遇到重复字符时，左指针向右移动，直到窗口中不再包含重复字符。
        while (isset($set[$c])) {
            unset($set[$s[$left]]);
            $left++;
        }
        $set[$c] = true;
        $ans = max($ans, $right - $left + 1);
        $right++;
    }
    return $ans;
}

// 调用
$str = 'sdf233rdfekdfkkdfkdkgkdfgggegfgmffdfdfeer343ferrfe';
$res = $this->lengthOfLongestSubstring($str);
dump($res);        // 6

注意事项

  • 窗口大小: 滑动窗口的大小是根据具体问题来确定的。
  • 数据类型: 滑动窗口可以处理各种类型的数据，包括数字、字符等。
  • 时间复杂度: 滑动窗口算法的时间复杂度通常是O(n)，其中n是输入数据的长度。
文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/sliding-window.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 滑动窗口
赏
评 论
 本篇
滑动窗口算法
滑动窗口算法
什么是滑动窗口算法？滑动窗口算法的核心思想是：维护一个固定大小的窗口，随着数据的不断输入，窗口不断向后滑动，从而达到对数据流进行局部统计或计算的目的。 应用场景 字符串处理: 查找最长无重复子串、字符串的排列等。 数组处理: 寻找数组中满足
2024-11-13 算法
PHP 算法 滑动窗口
下一篇 
PHP实现熔断机制
PHP实现熔断机制
什么是熔断机制？熔断机制是一种应对系统故障、防止级联故障的保护机制。当某个服务出现故障时，通过熔断机制，可以快速隔离故障服务，防止故障蔓延到整个系统，从而保证系统的稳定性。 熔断机制的核心要素 快速失败： 当服务不可用时，立即返回错误，防止
2024-11-13 系统设计
PHP 熔断
  目录
  目录
  目录
hexo