【leetcode】滑动窗口类问题_滑动窗口算法变种题目

滑动窗口是算法中一种重要的解题思想，通过分析力扣中的几道题目来学习滑动窗口的思想。

一、更贴合笔试的滑动窗口综合题

1.1 题目分析

题目链接：220. 存在重复元素 III

题目描述：

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例一：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
1
2

示例二：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
1
2

题目分析：

根据题意，对于任意一个位置 i（假设其值为 u），我们其实是希望在下标范围为 [max(0, i-k), i] 内找到值范围在 [u-t, u+t] 的数。

一个朴素的想法是每次遍历到任意位置 i 的时候，往后检查 k 个元素，但这样做的复杂度是O(nk) 的，会超时。

显然我们需要优化「检查后面 k 个元素」这一过程。

我们希望使用一个「有序集合」去维护长度为 k 的滑动窗口内的数，该数据结构最好支持高效「查询」与「插入/删除」操作：

• 查询：能够在「有序集合」中应用「二分查找」，快速找到「小于等于的最大值」和「大于等于 u 的最小值」（即「有序集合」中的最接近 u 的数）。
• 插入/删除：在往「有序集合」添加或删除元素时，能够在低于线性的复杂度内完成（维持有序特性）。

或许你会想到近似 操作的 HashMap，但注意这里我们需要找的是符合abs(nums[i] - nums[j]) <= t 的两个值，nums[i] 与 nums[j] 并不一定相等，而 HashMap 无法很好的支持「范围查询」操作。

我们还会想到「树」结构。

例如 AVL，能够让我们在最坏为 O(logk)的复杂度内取得到最接近 u 的值是多少，但本题除了「查询」以外，还涉及频繁的「插入/删除」操作（随着我们遍历 nums 的元素，滑动窗口不断右移，我们需要不断的往「有序集合」中删除和添加元素）。

简单采用 AVL 树，会导致每次的插入删除操作都触发 AVL 的平衡调整，一次平衡调整会伴随着若干次的旋转。

而红黑树则很好解决了上述问题：将平衡调整引发的旋转的次数从「若干次」限制到「最多三次」。

因此，当「查询」动作和「插入/删除」动作频率相当时，更好的选择是使用「红黑树」。

也就是对应到 Java 中的 TreeSet 数据结构（基于红黑树，查找和插入都具有折半的效率）。

1.2 滑动窗口+有序集合

实现方面，我们在有序集合 TreeSet 中查找大于等于 x−t 的最小的元素 y，如果 y 存在，且 y ≤ x+t，我们就找到了一对符合条件的元素。完成检查后，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 k，我们将有序集合中最早被插入的元素删除即可。

其他细节：由于 nums 中的数较大，会存在 int 溢出问题，我们需要使用 long 来存储。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // TreeSet,基于红黑树，查找和插入都具有折半的效率
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);  // 返回集合中大于或等于nums[i] - t的最小元素
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);  // 滑动窗口移动
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

TreeSet函数：

ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回 null.
floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.
remove(Object O) 删除指定元素
add(Object O) 添加元素
1
2
3
4

1.3 桶排序

上述解法无法做到线性的原因是：我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。

如果我们能够将 k 个数字分到 个桶的话，那么我们就能 O(1) 的复杂度确定是否有 [u - t, u + t] 的数字（检查目标桶是否有元素）。

具体的做法为：令桶的大小为 size = t + 1，根据 u 计算所在桶编号：

• 如果已经存在该桶，说明前面已有 [u - t, u + t] 范围的数字，返回 true
• 如果不存在该桶，则检查相邻两个桶的元素是有[u - t, u + t]范围的数字，如有 返回 true
• 建立目标桶，并删除下标范围不在 [max(0, i-k), i] 内的桶

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 桶排序
        long size;
        int n = nums.length;
        Map<Long, Long> map = new HashMap<>();
        size = t + 1L;
        for (int i = 0; i < n; i++) {
            long u = nums[i] * 1L;
            long idx = getIdx(u, size);
            // 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if (map.containsKey(idx)) return true;
            // 检查相邻的桶
            long l = idx - 1, r = idx + 1;
            if (map.containsKey(l) && u - map.get(l) <= t) return true;
            if (map.containsKey(r) && map.get(r) - u <= t) return true;
            // 建立目标桶
            map.put(idx, u);
            // 移除下标范围不在 [max(0, i - k), i) 内的桶
            if (i >= k) map.remove(getIdx(nums[i - k] * 1L, size));
        }
        return false;
    }
    long getIdx(long u, long size) {
        return u >= 0 ? u / size : ((u + 1) / size) - 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

理解 getIdx() 逻辑

1. 为什么 size 需要对 t 进行 +1 操作？

   目的是为了确保差值小于等于 t 的数能够落到一个桶中。

   举个

   声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/276924