專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

昨天上午由于五一買(mǎi)票的原因，結(jié)果中午的時(shí)候京東外賣(mài)也崩了，據(jù)多位用戶反饋，京東外賣(mài)頁(yè)面無(wú)法查看商品信息，頁(yè)面顯示“網(wǎng)絡(luò)請(qǐng)求失敗”。

很快京東外賣(mài)官方發(fā)文稱：由于百億補(bǔ)貼活動(dòng)過(guò)于火爆，京東外賣(mài)的流量達(dá)到了平時(shí)的4倍，系統(tǒng)出現(xiàn)了不到 20分鐘的短暫異常，影響了大家下單。目前已經(jīng)緊急修復(fù)了問(wèn)題，服務(wù)已經(jīng)全面恢復(fù)。

流量達(dá)到平時(shí) 4 倍就崩潰了，說(shuō)明京東外賣(mài)系統(tǒng)設(shè)計(jì)的還是有問(wèn)題的。但不管怎樣我還是希望京東外賣(mài)能夠做起來(lái)，不希望美團(tuán)一家獨(dú)大。

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

來(lái)看下今天的算法題，這題是LeetCode的第1456題：定長(zhǎng)子串中元音的最大數(shù)目，難度是中等。

給你字符串 s 和整數(shù) k 。請(qǐng)返回字符串 s 中長(zhǎng)度為 k 的單個(gè)子字符串中可能包含的最大元音字母數(shù)。英文中的 元音字母 為（a, e, i, o, u）。

示例1：

輸入：s = "abciiidef", k = 3 輸出：3 解釋：子字符串 "iii" 包含 3 個(gè)元音字母。

示例2：

輸入：s = "aeiou", k = 2 輸出：2 解釋：任意長(zhǎng)度為 2 的子字符串都包含 2 個(gè)元音字母。

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

• s 由小寫(xiě)英文字母組成

• 1 <= k <= s.length

問(wèn)題分析

這題讓計(jì)算長(zhǎng)度為 k 的子串中元音字母的最大個(gè)數(shù)，實(shí)際上這就是一道滑動(dòng)窗口問(wèn)題，并且窗口大小還是固定的，長(zhǎng)度是 k 。

剛開(kāi)始的時(shí)候只滑動(dòng)窗口的右邊界，然后累加窗口中元音字母的個(gè)數(shù) cnt ，當(dāng)窗口長(zhǎng)度達(dá)到 k 的時(shí)候，記錄下窗口中元音字母的個(gè)數(shù)。

接著窗口的兩邊同時(shí)往右滑動(dòng)，以確保窗口的長(zhǎng)度始終為 k 。窗口的右邊是添加字母，窗口的左邊是移出字母，如果添加的是元音字母，則 cnt 要加 1 ，如果移除的是元音字母，則 cnt 要減 1 。后續(xù)每次滑動(dòng)的時(shí)候都要保存窗口中元音字母的最大個(gè)數(shù)。

關(guān)于滑動(dòng)窗口的問(wèn)題之前我也做過(guò)總結(jié)，常見(jiàn)的一般有三種，一種是可大可小窗口，一種是固定長(zhǎng)度窗口，還一種是只增不減窗口，每種窗口都有一個(gè)固定的模板，具體可以看下《算法秘籍》中的總結(jié)，而這題就是固定長(zhǎng)度窗口，根據(jù)模板代碼，稍微修改一下即可。

JAVA：

public int maxVowels(String s, int k) {     int left = 0, right = 0, n = s.length();     int cnt = 0;// 當(dāng)前窗口中元音字母的個(gè)數(shù)     int ans = 0;// 記錄窗口內(nèi)的最大元音字母?jìng)€(gè)數(shù)     while (right < n) {         // 判斷窗口右邊是否是元音字母，如果是就加上         cnt += isVowel(s.charAt(right++));         // 窗口長(zhǎng)度等于 k 的時(shí)候開(kāi)始記錄最大元音字母?jìng)€(gè)數(shù)         if (right - left == k) {             ans = Math.max(ans, cnt);// 保存最大值             // 因?yàn)槭枪潭ù翱冢翱谧筮叺脑匾龃翱?            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;// 當(dāng)前窗口中元音字母的個(gè)數(shù)         int ans = 0;// 記錄窗口內(nèi)的最大元音字母?jìng)€(gè)數(shù)         while (right < n) {             // 判斷窗口右邊是否是元音字母，如果是就加上             cnt += isVowel(s[right++]);             // 窗口長(zhǎng)度等于 k 的時(shí)候開(kāi)始記錄最大元音字母?jìng)€(gè)數(shù)             if (right - left == k) {                 ans = max(ans, cnt);// 保存最大值                 // 因?yàn)槭枪潭ù翱冢翱谧筮叺脑匾龃翱?                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;     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫(xiě)算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。