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

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

最近一網友發文稱自己的離職證明上有負面消息，該怎么辦？不知道大家離職的時候有沒有遇到這種情況，如果遇到這種情況，說明這hr很不專業，可以溝通讓她修改，如果拒不修改，直接起訴就行了。

根據《勞動合同法》第 50 條、《勞動合同法實施條例》第 24 條，離職證明需載明：勞動合同期限，解除 / 終止勞動合同日期，工作崗位，在本單位的工作年限。禁止記載：離職原因、員工評價、紀律處分等負面信息（除非雙方協商一致且不違反法律）。若公司擅自寫入 “曠工”“能力不足” 等非法定內容，可能構成違法約定或侵犯勞動者權益（如影響后續求職）。

所以離職證明上是不能對員工有負面評價的，離職爭取自己權益的時候不要怕離職證明有負面消息而瞻前顧后，投鼠忌器。

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

來看下今天的算法題，這題是LeetCode的第1482題：制作 m 束花所需的最少天數，難度是中等。

給你一個整數數組 bloomDay，以及兩個整數 m 和 k ?，F需要制作 m 束花。制作花束時，需要使用花園中相鄰的 k 朵花 。

花園中有 n 朵花，第 i 朵花會在 bloomDay[i] 時盛開，恰好可以用于一束花中。請你返回從花園中摘 m 束花需要等待的最少的天數。如果不能摘到 m 束花則返回 -1 。

示例1：

輸入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 輸出：12 解釋：要制作 2 束花，每束需要 3 朵。 花園在 7 天后和 12 天后的情況如下： 7 天后：[x, x, x, x, _, x, x] 可以用前 3 朵盛開的花制作第一束花。但不能使用后 3 朵盛開的花，因為它們不相鄰。 12 天后：[x, x, x, x, x, x, x] 顯然，我們可以用不同的方式制作兩束花。

示例2：

輸入：bloomDay = [1,10,3,10,2], m = 3, k = 2 輸出：-1 解釋：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花園中只有 5 朵花，無法滿足制作要求，返回 -1 。

• bloomDay.length == n

• 1 <= n <= 10^5

• 1 <= bloomDay[i] <= 10^9

• 1 <= m <= 10^6

• 1 <= k <= n

問題分析

這題說的是制作每束花需要 k 朵花，并且每朵花有一個開花的時間，問制作 m 束花需要的最少天數。

制作 m 束花總共需要 k*m 朵花，如果總的花束不夠，就算等到天荒地老也制作不了 m 束花，我們可以直接返回 -1 。

如果花夠了，這里怎么來查找最小時間呢？這里我們可以通過二分法查找，二分查找的最小值和最大值分別是數組中元素的最小值和最大值。每次取中間的值，檢查能不能制作 m 束花。

比如區間是[10,100]，我們可以先判斷55能不能滿足條件，如果不能，則區間范圍變成[56,100]，如果能滿足條件，則區間范圍變成[10,55]，注意這里的55不能排除掉，通過二分法查找，最后區間長度為 1 的時候，這個區間的值就是我們要求的結果。

JAVA：

public int minDays(int[] bloomDay, int m, int k) {     int n = bloomDay.length;     if (n < 1L * m * k)// 防止溢出，轉為long類型         return -1;     // 找出數組中的最大值和最小值。     int low = Integer.MAX_VALUE, high = 0;     for (int num : bloomDay) {         low = Math.min(low, num);         high = Math.max(high, num);     }     while (low < high) {// 二分查找。         int mid = (high - low) / 2 + low;         if (check(bloomDay, mid, m, k)) {             high = mid;         } else {             low = mid + 1;         }     }     return low; } // 檢查days天之后是否可以制作 m 束花。 private boolean check(int[] bloomDay, int days, int m, int k) {     int cnt = 0;// 花束的數量     int flowers = 0;// 制作花束使用的花朵     int n = bloomDay.length;     for (int i = 0; i < n && cnt < m; i++) {         if (bloomDay[i] <= days) {// 第 i 朵盛開了             flowers++;             if (flowers == k) {                 cnt++;// k 朵花制作一個花束。                 flowers = 0;             }         } else {// 第 i 朵還沒有盛開。             flowers = 0;         }     }     return cnt >= m; }

C++：

public:     int minDays(vector

 &bloomDay, int m, int k) {         int n = bloomDay.size();         if (n < 1L * m * k)// 防止溢出，轉為long類型             return-1;         // 找出數組中的最大值和最小值。         int low = INT_MAX, high = 0;         for (int num: bloomDay) {             low = min(low, num);             high = max(high, num);         }         while (low < high) {// 二分查找。             int mid = (high - low) / 2 + low;             if (check(bloomDay, mid, m, k)) {                 high = mid;             } else {                 low = mid + 1;             }         }         return low;     }     // 檢查days天之后是否可以制作 m 束花。     bool check(vector

 &bloomDay, int days, int m, int k) {         int cnt = 0;// 花束的數量         int flowers = 0;// 制作花束使用的花朵         int n = bloomDay.size();         for (int i = 0; i < n && cnt < m; i++) {             if (bloomDay[i] <= days) {// 第 i 朵盛開了                 flowers++;                 if (flowers == k) {                     cnt++;// k 朵花制作一個花束。                     flowers = 0;                 }             } else {// 第 i 朵還沒有盛開。                 flowers = 0;             }         }         return cnt >= m;     }

筆者簡介

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