about Sliding Window3
Wed, Sep 1, 2021
6-minute read
Sliding Window pattern in algorithm, 滑动窗口套路
滑动窗口更多处理连续问题， “Longest Substring“， ”Subarray“
Maximum Values Of Size K Sliding Windowss
😼😼😼😼
和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
思路知道，但是代码不优雅，而且有可能结果是 0， 因为始终达不到
target， 所以 sum 小于 target，res 就是 0，所以条件函数里只计算 sum >= target, 更新 res， slow 指针更新
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE;
int slow = 0, fast = 0;
int sum = 0;
while (fast < nums.length) {
sum += nums[fast];
while (sum >= target) {
res = Math.min(res, fast - slow + 1);
sum -= nums[slow];
slow++;
}
fast++;
}
return res == Integer.MAX_VALUE? 0 : res;
}
}
乘积小于 K 的子数组
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1：
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
个数的规律没有推算出来
class Solution {
public int minSubArrayLen(int target, int[] nums) {
if ( k == 0) {
return 0;
}
int slow = 0, fast = 0;
int sum = 1;
int count = 0;
while ( fast < nums.length) {
sum *= nums[fast];
while (slow <= fast && sum >= k){
sum /= nums[slow++];
}
count += (fast - slow + 1);
fast++;
}
return count;
}
}
滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
移动窗口找最大值考虑单调队列, 队列里的元素一定是要排序的，而且要最大值放在出队口
设计单调队列的时候，pop，和 push 操作要保持如下规则：
pop(value)：如果窗口移除的元素 value 等于单调队列的出口元素，那么队列弹出元素，否则不用任何 操作
push(value)：如果 push 的元素 value 大于入口元素的数值，那么就将队列入口的元素弹出，直到 push 元素的数值小于等于队列入口元素的数值为止
空间复杂度就很简单了，就是窗口的大小 O(k)O(k)。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>();
int[] res = new int[n - k + 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
if (i >= k - 1) {
res[index++] = nums[deque.peek()];
}
}
return res;
}
}
里面不是一个数据
nums = [1, 2, 3, 2, 4, 2, 1] i i
deque: [2, 3]
当 i = 4， 5， 6 时候，数据是 4 2 1
全部塞入 deque 中
deque：[4, 5, 6]
设计 api 的方法
class MyDeque {
Deque<Integer> deque = new ArrayDeque<>();
// 要弹出的是否是队列出口的数值，相等就弹出
void poll(int val) {
if(!deque.isEmpty() && deque.peek() == val) {
deque.poll();
}
}
void push(int val) {
if(!deque.isEmpty() && deque.peekLast() < val) {
deque.removeLast();
}
deque.add(val);
}
void peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[n - k + 1];
int index = 0;
MyDeque deque = new MyDeque<>();
for (int i = 0; i < k; i++) {
deque.add(nums[i]);
}
res[index++] = deque.peek();
for (int i = k; i < nums.length; i++) {
deque.poll(nums[i - k]);
deque.add(nums[i ]);
res[index++] = deque.peek();
}
return res;
}
}
值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
slide window
时间复杂度：TreeSet 基于红黑树，查找和插入都是 O(\log{k})O(logk) 复杂度。整体复杂度为 O(n\log{k})O(nlogk) 空间复杂度：O(k)O(k)
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0) return false;
TreeSet<Long> set = new TreeSet<>();
set.add((long) nums[0]);
for (int i = 1; i < nums.length; i++) {
if (i > k) set.remove((long) nums[i - k - 1]);
long left = (long) nums[i] - t;
long right = (long) nums[i] + t;
if (left <= right && !set.subSet(left, right + 1).isEmpty()) return true;
set.add((long) nums[i]);
}
return false;
}
int n = nums.length;
TreeSet<Long> ts = new TreeSet<>();
for (int i = 0; i < n; i++) {
Long u = nums[i] * 1L;
// 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
Long l = ts.floor(u);
// 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
Long r = ts.ceiling(u);
if(l != null && u - l <= t) return true;
if(r != null && r - u <= t) return true;
// 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
ts.add(u);
if (i >= k) ts.remove(nums[i - k] * 1L);
}
return false;
}
桶排序 上述解法无法做到线性的原因是：我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。
如果我们能够将 k 个数字分到 kk 个桶的话，那么我们就能 O(1)O(1) 的复杂度确定是否有 [u - t, u + t][u−t,u+t] 的数字（检查目标桶是否有元素）。
具体的做法为：令桶的大小为 size = t + 1size=t+1，根据 u 计算所在桶编号：
如果已经存在该桶，说明前面已有 [u - t, u + t][u−t,u+t] 范围的数字，返回 true 如果不存在该桶，则检查相邻两个桶的元素是有 [u - t, u + t][u−t,u+t] 范围的数字，如有 返回 true 建立目标桶，并删除下标范围不在 [max(0, i - k), i)[max(0,i−k),i) 内的桶
slide window
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> d = new HashMap<>();
long w = (long)t + 1;
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
if (d.containsKey(m))
return true;
if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
return true;
if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
return true;
d.put(m, (long)nums[i]);
if (i >= k) d.remove(getID(nums[i - k], w));
}
return false;
}
private long getID(long i, long w) {
return i < 0 ? (i + 1) / w - 1 : i / w;
}
}
Maximum Values Of Size K Sliding Windowss
Given an integer array A and a sliding window of size K, find the maximum value of each window as it slides from left to right.
Assumptions
The given array is not null and is not empty
K >= 1, K <= A.length
Examples
A = {1, 2, 3, 2, 4, 2, 1}, K = 3, the windows are {{1,2,3}, {2,3,2}, {3,2,4}, {2,4,2}, {4,2,1}},
and the maximum values of each K-sized sliding window are [3, 3, 4, 4, 4]
public List<Integer> maxWindows(int[] array, int k) {
List<Integer> res = new ArrayList<>();
Deque<Integer> stack= new ArrayDeque<>();
for (int fast = 0; fast < array.length; fast++) {
while(!stack.isEmpty() && stack.peek() <= fast - k ) {
stack.pollFirst();
}
while(!stack.isEmpty() && array[stack.peekLast()] < array[fast]) {
stack.pollLast();
}
stack.offerLast(fast);
if (fast >= k - 1) {
res.add(array[stack.peekFirst()]);
}
}
return res;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/MPnaiL
感谢：她们都有题库在 github 上直接有，都是大神
