京东外卖崩了，回应来了。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

昨天上午由于五一买票的原因，结果中午的时候京东外卖也崩了，据多位用户反馈，京东外卖页面无法查看商品信息，页面显示“网络请求失败”。

很快京东外卖官方发文称：由于百亿补贴活动过于火爆，京东外卖的流量达到了平时的4倍，系统出现了不到 20分钟的短暂异常，影响了大家下单。目前已经紧急修复了问题，服务已经全面恢复。

流量达到平时 4 倍就崩溃了，说明京东外卖系统设计的还是有问题的。但不管怎样我还是希望京东外卖能够做起来，不希望美团一家独大。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1456题：定长子串中元音的最大数目，难度是中等。

给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。英文中的 元音字母 为（a, e, i, o, u）。

示例1：

输入：s = "abciiidef", k = 3 输出：3 解释：子字符串 "iii" 包含 3 个元音字母。

示例2：

输入：s = "aeiou", k = 2 输出：2 解释：任意长度为 2 的子字符串都包含 2 个元音字母。

• 1 <= s.length <= 10^5

• s 由小写英文字母组成

• 1 <= k <= s.length

问题分析

这题让计算长度为 k 的子串中元音字母的最大个数，实际上这就是一道滑动窗口问题，并且窗口大小还是固定的，长度是 k 。

刚开始的时候只滑动窗口的右边界，然后累加窗口中元音字母的个数 cnt ，当窗口长度达到 k 的时候，记录下窗口中元音字母的个数。

接着窗口的两边同时往右滑动，以确保窗口的长度始终为 k 。窗口的右边是添加字母，窗口的左边是移出字母，如果添加的是元音字母，则 cnt 要加 1 ，如果移除的是元音字母，则 cnt 要减 1 。后续每次滑动的时候都要保存窗口中元音字母的最大个数。

关于滑动窗口的问题之前我也做过总结，常见的一般有三种，一种是可大可小窗口，一种是固定长度窗口，还一种是只增不减窗口，每种窗口都有一个固定的模板，具体可以看下《算法秘籍》中的总结，而这题就是固定长度窗口，根据模板代码，稍微修改一下即可。

JAVA：

public int maxVowels(String s, int k) {     int left = 0, right = 0, n = s.length();     int cnt = 0;// 当前窗口中元音字母的个数     int ans = 0;// 记录窗口内的最大元音字母个数     while (right < n) {         // 判断窗口右边是否是元音字母，如果是就加上         cnt += isVowel(s.charAt(right++));         // 窗口长度等于 k 的时候开始记录最大元音字母个数         if (right - left == k) {             ans = Math.max(ans, cnt);// 保存最大值             // 因为是固定窗口，窗口左边的元素要出窗口             cnt -= isVowel(s.charAt(left++));         }     }     return ans; } // 是元音字母返回1，否则返回0 private int isVowel(char ch) {     return ch == 'a' || ch == 'e' || ch == 'i'             || ch == 'o' || ch == 'u' ? 1 : 0; }

C++：

public:     int maxVowels(string s, int k) {         int left = 0, right = 0, n = s.length();         int cnt = 0;// 当前窗口中元音字母的个数         int ans = 0;// 记录窗口内的最大元音字母个数         while (right < n) {             // 判断窗口右边是否是元音字母，如果是就加上             cnt += isVowel(s[right++]);             // 窗口长度等于 k 的时候开始记录最大元音字母个数             if (right - left == k) {                 ans = max(ans, cnt);// 保存最大值                 // 因为是固定窗口，窗口左边的元素要出窗口                 cnt -= isVowel(s[left++]);             }         }         return ans;     }     // 是元音字母返回1，否则返回0     int isVowel(char ch) {         return ch == 'a' || ch == 'e' || ch == 'i'                || ch == 'o' || ch == 'u' ? 1 : 0;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。