五月集训（第6天）——滑动窗口

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

滑动窗口算法一般用于数组问题中，大概内容就是定义两个指针，中间的元素就是窗口；窗口长度和两个指针的变化是关键难点。

二、课堂习题

这里的题均出自《算法零基础100讲》
临近期末，学业繁忙，大家可以自行去专栏查找习题。

三、作业

1984. 学生分数的最小差值
1876. 长度为三且各字符不同的子字符串
1839. 所有元音按顺序排布的最长子字符串
1052. 爱生气的书店老板
解题思路：

1. 将数组排序，因为窗口长度是固定的已经给出，所以两个指针固定好，不断向右滑动寻找不同窗口内最大值和最小值的最小差值。
2. 窗口长度固定为3，所以定义两个指针不断向右滑，对每次的新窗口进检查字符是否各不相同，若是计数器+1 。
3. 窗口长度不固定，定义一个旗帜来记录每次窗口出现的不同元音字符个数，同时定义两个指针i,j从头部开始，若j元素>i元素，j++，相反则重新记录旗帜，同时i=j，当出现了5个元音字符时计算长度。
4. 计算顾客数组在老板不生气时出现的人数ans，然后将数组元素原地改为0，然后再定义两个指针，窗口长度为minutes，寻找窗口出现的最大人数max，最后将ans+max返回。
   代码以及结果：

class Solution {    public int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int min = Integer.MAX_VALUE; int i = 0,j = k-1; while(j < nums.length){     min = Math.min(min,nums[j] - nums[i]);     ++i;++j; } return min;    }}

class Solution {    public int countGoodSubstrings(String s) { int left = 0; int right = 2; int i, j; boolean flags = true; int count = 0; while (right < s.length()) {   flags = true;     for (i = left; i < left + 2; i++)     {  for (j = i + 1; j <= left + 2; j++)  {      if (s.charAt(i) == s.charAt(j))      {   flags = false;   break;      }  }     }     if (flags)     {  count++;     }     left++;     right++; } return count;    }}

class Solution {    public int longestBeautifulSubstring(String word) { int f=1,max=0; int i = 0,j = 1; while(j < word.length()){     if(word.charAt(j)<word.charAt(j-1)){  i=j;  f=1;     }else if(word.charAt(j)>word.charAt(j-1)){  f++;     }     if(f==5){  max=Math.max(max, j-i+1);     }     ++j; } return max;    }}

class Solution {    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int n = customers.length, ans = 0; for (int i = 0; i < n; i++) {     if (grumpy[i] == 0) {  ans += customers[i];  customers[i] = 0;     } } int temp = 0, max = 0; for (int i = 0; i < n; i++) {     temp += customers[i];     if (i >= minutes) temp -= customers[i - minutes];     max = Math.max(max, temp); } return ans + max;    }}

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
训练题目预计到下个月的集训才能开始写啦QAQ