專欄：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算法文檔 。