今天做力扣學(xué)習(xí)計劃的“二分查找基礎(chǔ)”的時候，碰到一道有意思的題目：1562. 查找大小為 M 的最新分組?，可以使用四種不同的思路（單調(diào)棧、模擬、二分查找、并查集）進(jìn)行解答，非常適合學(xué)習(xí)與練習(xí)，在此給大家分享一下。

話說最近一直沒有更新文章，主要就是因為力扣上面不小心開了好幾個學(xué)習(xí)計劃同時進(jìn)行，一天得寫十幾道題，都快寫吐了。不過這周估計可以全部解決掉，以后再也不這樣搞了。主要都是中等和簡單題，新手用來學(xué)習(xí)不錯，我這樣刷起來有點費時間了。（不過倒是順便練了練 Kotlin 和 C#）

如果你要練學(xué)習(xí)計劃的話，可以提醒一下，其實當(dāng)天沒寫完也是可以的，可以后面補(bǔ)（如果到了時間還沒寫完那就不知道是否可以了），而且可以提前寫后面未解鎖的題目，提交通過的話，后面也是不需要重復(fù)寫的。

1 題目

1562. 查找大小為 M 的最新分組 難度：中等

給你一個數(shù)組 arr ，該數(shù)組表示一個從 1 到 n 的數(shù)字排列。有一個長度為 n 的二進(jìn)制字符串，該字符串上的所有位最初都設(shè)置為 0 。

在從 1 到 n 的每個步驟 i 中（假設(shè)二進(jìn)制字符串和 arr 都是從 1 開始索引的情況下），二進(jìn)制字符串上位于位置 arr[i] 的位將會設(shè)為 1 。

給你一個整數(shù) m ，請你找出二進(jìn)制字符串上存在長度為 m 的一組 1 的最后步驟。一組 1 是一個連續(xù)的、由 1 組成的子串，且左右兩邊不再有可以延伸的 1 。

返回存在長度 恰好 為 m 的 一組 1 ?的最后步驟。如果不存在這樣的步驟，請返回 -1 。

示例 1：

輸入：arr?=?[3,5,1,2,4],?m?=?1
輸出：4
解釋：
步驟?1："00100"，由?1?構(gòu)成的組：["1"]
步驟?2："00101"，由?1?構(gòu)成的組：["1",?"1"]
步驟?3："10101"，由?1?構(gòu)成的組：["1",?"1",?"1"]
步驟?4："11101"，由?1?構(gòu)成的組：["111",?"1"]
步驟?5："11111"，由?1?構(gòu)成的組：["11111"]
存在長度為?1?的一組?1?的最后步驟是步驟?4?。


示例 2：

輸入：arr?=?[3,1,5,4,2],?m?=?2
輸出：-1
解釋：
步驟?1："00100"，由?1?構(gòu)成的組：["1"]
步驟?2："10100"，由?1?構(gòu)成的組：["1",?"1"]
步驟?3："10101"，由?1?構(gòu)成的組：["1",?"1",?"1"]
步驟?4："10111"，由?1?構(gòu)成的組：["1",?"111"]
步驟?5："11111"，由?1?構(gòu)成的組：["11111"]
不管是哪一步驟都無法形成長度為?2?的一組?1?。


示例 3：

輸入：arr?=?[1],?m?=?1
輸出：1


示例 4：

輸入：arr?=?[2,1],?m?=?2
輸出：2


提示：

• n == arr.length

• 1 <= n <= 10^5

• 1 <= arr[i] <= n

• arr 中的所有整數(shù) 互不相同

• 1 <= m <= arr.length

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/find-latest-group-of-size-m
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2 時間順序單調(diào)棧法

首先介紹一個相對冷門的單調(diào)棧的題解：https://leetcode.cn/problems/find-latest-group-of-size-m/solution/er-fen-zhen-bu-shou-huan-shi-dan-diao-zh-375g/，感覺這個思路確實和其他模擬思路題解相比挺新穎的，除了這一篇，基本就沒有提到的了。只是原題解代碼寫的有點冗雜了，遮蔽了其思路主旨。我使用 Scala 一邊重構(gòu)了一下代碼，一邊理解思路，終于看懂了。感覺最后的成品代碼更方便大家理解，就也分享一下吧~ （用 C# 也補(bǔ)了一份實現(xiàn)，方便熟悉 C++ 或 Java 的同學(xué)閱讀）

具體思路可以參考注釋，還是不懂的話，大致介紹一下：

• 首先將 arr 處理為存儲對應(yīng)索引的 1 的插入時間的數(shù)組 t。這里有個特殊處理的 t[0] 和 t[arr.length + 1] 取值 Int 最大值，簡化后續(xù)處理。

• 然后按照時間順序遞增（對應(yīng)變量 i，范圍為 [0, arr.length + 1]）檢查單調(diào)棧，如果棧里非空且 t[棧頂] < t[i] 說明在 i 左側(cè)的 1 插入時間早于 i 處的 1，所以我們就可以把這個連接在一起的時間點算出來。我們的目的是找到最晚的一個連接長度為 m 的時間點。

• 長度就是對應(yīng) i - 下一個棧頂 - 1，因為下一個棧頂?shù)挠覀?cè)就是相當(dāng)于當(dāng)前連接的全 1 序列最左端。當(dāng)長度等于 m 時我們可以計算出來目前全 1 序列首次出現(xiàn)的時間，即 t[下一個棧頂], t[i] 的最小值

• 重復(fù)以上邏輯就可以將最大的結(jié)果找出來。

看懂了就不禁感嘆：“妙啊，妙啊……”，只是理解起來沒有模擬始末節(jié)點數(shù)組法直觀。代碼如下：

Scala

C#

3 模擬始末節(jié)點數(shù)組法

給官方題解的方法起了一個這個名字，感覺應(yīng)該比較好理解吧。具體原理可以看 官方題解：https://leetcode.cn/problems/find-latest-group-of-size-m/solution/cha-zhao-da-xiao-wei-m-de-zui-xin-fen-zu-by-leetco/，Scala 的實現(xiàn)的話直接看代碼吧：

4 題外話

這道題目我是從“二分查找基礎(chǔ)”的學(xué)習(xí)計劃過來的，但是包括官方題解在內(nèi)的大多數(shù)題解沒用到二分查找，真是笑死……

順便提一下，其實是有二分查找的思路的，具體來說就是對應(yīng)這篇 Java 用到了 TreeSet 的題解：https://leetcode.cn/problems/find-latest-group-of-size-m/solution/fan-xiang-qjing-wei-shen-sui-ran-wo-yun-xing-shi-j/ 以及這篇 C++ 用到了 set 的題解：https://leetcode.cn/problems/find-latest-group-of-size-m/solution/zheng-xiang-si-wei-by-sui-xin-yuan-oaiv/ ，逆向從全 1 的時間往回查的思路也還是挺妙的。我就先懶得自己用 Scala 試了，看懂單調(diào)棧的那篇原題解耗費太多腦細(xì)胞，讓我緩緩。（笑）

另外，其實并查集顯然也可以做，合并集合（全為 1 的序列）并計數(shù)統(tǒng)計集合大小，典型并查集題目嘛。并查集不清楚的話，可以參考上面 C++二分的那篇題解，也提到了并查集。（其實我自己首先想到就是這個思路，但自己是二分查找進(jìn)來的，就感覺套并查集套模板有點沒意思了，后來就看題解去看二分咋寫了。看到逆向基本就懂了二分是啥思路，就感覺沒啥必要自己寫了，就去學(xué)習(xí)前面分享的這兩種寫法了）

順便分享一下自己簡單的并查集的 Java、Scala、Kotlin 模板吧，套起來用還是很方便的：

Java

Scala

Kotlin