文章目录
- 📃滑动窗口
- 📜基本概念
- 📜核心思路
- ✍最大连续1的个数 III
- ✍水果成篮
📃滑动窗口
📜基本概念
滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。
分类：窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。
应用：什么情况可以用滑动窗口来解决实际问题呢？
- 一般给出的数据结构是数组或者字符串
- 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
- 该问题本身可以通过暴力求解
📜核心思路
窗口的形成
在具体使用之前，我们知道窗口实际是两个指针之间形成的区域，那关键就是这两个指针是如何移动的。
- 初始时，左右指针left,right都指向第0个元素，窗口为[left,right)，注意这里是左闭右开，因此初始窗口[0,0)区间没有元素，符合我们的初始定义
- 开始循环遍历整个数组元素，判断当前right指针是否超过整个数组的长度，是退出循环，否则执行第3步
- 然后right指针开始向右移动一个长度，并更新窗口内的区间数据
- 当窗口区间的数据满足我们的要求时，右指针right就保持不变，左指针left开始移动，直到移动到一个不再满足要求的区间时，left不再移动位置
- 执行第2步
✍最大连续1的个数 III
力扣链接: 最大连续1的个数 III
分析：
本题的难点在于如何对翻转K进行处理，如果我们按照一个数一个数来翻转的话，那就太麻烦了，没有get到这道题考察的知识点。
这里我们可以将翻转K个0转化理解为在一个数组中，找到一段连续的数字，其中这组数字拥有不超过K个0。这是就可以归为滑动窗口来解决这个问题了。
public int longestOnes(int[] nums, int k) {
int left = 0;
int right = 0;
int count = 0;
int max = 0;
while (right < nums.length){
if (nums[right] == 0){
count++;
}
while (count > k){
if (nums[left] == 0){
count--;
}
left++;
}
max = Math.max(max,right-left+1);
right++;
}
return max;
}
✍水果成篮
力扣链接: 水果成篮
分析
看完题目是不是有点蒙，那么看示例我们就很轻松的可以理解了。我现在来简要概括一下：
在一个数组中，查找一段连续的数组，这段数组中最多只能有两种数字。
简单理解完题目后，我们还是可以用滑动窗口的思想来做，但这道题与第一道并不相同，本题可以拥有两种数字，这时我们引入哈希的思想来处理这个问题。如果你没有学过哈希，那么也可以用数组来代替哈希。
public int totalFruit(int[] fruits) {
int ret = 0;
Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
for (int right = 0,left = 0; right < fruits.length; right++) {
int in = fruits[right];
hash.put(in,hash.getOrDefault(in,0)+1);
while (hash.size() > 2){
int out = fruits[left];
hash.put(out,hash.get(out)-1);
if (hash.get(out) == 0){
hash.remove(out);
}
left++;
}
ret = Math.max(ret,right - left +1);
}
return ret;
}
以数组来代替哈希：
public int totalFruit(int[] fruits) {
int n = fruits.length;
int[] hash = new int[n+1];
int ret = 0;
for (int right = 0,left = 0,kinds = 0; right < n; right++) {
int in = fruits[right];
if (hash[in] == 0) kinds++;
hash[in]++;
while (kinds > 2){
int out = fruits[left];
hash[out]--;
if (hash[out] == 0)kinds--;
left++;
}
ret = Math.max(ret,right-left+1);
}
return ret;
}
