專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

據某官方媒體報道，一企業為了裁員，讓人事假扮獵頭誘導老員工離職，此前該公司還以業績不達標為由將員工工資從上萬元降到3000，以此來達到裁員的目的。為了裁員真的是煞費苦心，無所不用其極，從未見過如此厚顏無恥的企業。

法院判決的結果是違法解除勞動合同，估計最多也就給點賠償，不知道會不會受到懲罰。所以如果大家沒有投簡歷，有獵頭找到你，要確認該獵頭是不是公司hr，或者是公司安排的其他人員，要擦亮眼睛，辨識真偽。

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

來看下今天的算法題，這題是LeetCode的第1493題：刪掉一個元素以后全為 1 的最長子數組，難度是中等。

給你一個二進制數組 nums ，你需要從中刪掉一個元素。請你在刪掉元素的結果數組中，返回最長的且只包含 1 的非空子數組的長度。如果不存在這樣的子數組，請返回 0 。

示例1：

輸入：nums = [0,1,1,1,0,1,1,0,1] 輸出：5 解釋：刪掉位置 4 的數字后，[0,1,1,1,1,1,0,1] 的最長全 1 子數組為 [1,1,1,1,1] 。

示例2：

輸入：nums = [1,1,1] 輸出：2 解釋：你必須要刪除一個元素。

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

• nums[i] 要么是 0 要么是 1 。

問題分析

這題說的是給定一個二進制數組，從中刪除一個元素的情況下，返回最長的全為 1 的子數組長度。

這是一道典型的滑動窗口問題，滑動的時候累加窗口中元素的和sum：

1，如果窗口的長度len等于sum的值，說明窗口中的元素全部為 1 。

2，如果窗口的長度len=sum+1，說明窗口中只有 1 個 0 ，其他都是 1 。

3，如果窗口的長度len>sum+1，說明窗口中 0 的個數大于 1 ，只有這種情況下才會滑動窗口的左邊界。

最后窗口的長度就是我們要求的解，這個窗口是只增不減窗口，就是窗口的大小只能增大不能減小，具體可以看下中對滑動窗口的三個總結。

JAVA：

publicintlongestSubarray(int[] nums){     int left = 0, right = 0, n = nums.length;     int sum = 0;// 窗口中元素的和     while (right < n) {         sum += nums[right];// 累加窗口中元素的和         if (sum < right - left)             sum -= nums[left++];         right++;     }     // 因為在最后right執行了加 1 ，所以窗口的     // 長度是right-left，還要減去一個刪除的字符。     return right - left - 1; }

C++：

public:     intlongestSubarray(vector

 &nums){         int left = 0, right = 0, n = nums.size();         int sum = 0;// 窗口中元素的和         while (right < n) {             sum += nums[right];// 累加窗口中元素的和             if (sum < right - left)                 sum -= nums[left++];             right++;         }         // 因為在最后right執行了加 1 ，所以窗口的         // 長度是right-left，還要減去一個刪除的字符。         return right - left - 1;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。