要刪除以使數組排序的最短子數組

1574。刪除最短子數組以使數組排序

難度：中

主題：陣列、兩個指標、二分查找、堆疊、單調堆疊

給定一個整數數組 arr，從 arr 中刪除一個子數組（可以為空），使得 arr 中的剩餘元素非遞減。

傳回要刪除的最短子數組的長度.

子數組是數組的連續子序列。

範例1：

• 輸入： arr = [1,2,3,10,4,2,3,5]
• 輸出： 3
• 解釋： 我們可以刪除的最短子數組是長度為 3 的 [10,4,2]。之後的剩餘元素將是已排序的 [1,2,3,3,5]。
  • 另一個正確的解是刪除子數組 [3,10,4]。

範例2：

• 輸入： arr = [5,4,3,2,1]
• 輸出： 4
• 解釋：由於陣列是嚴格遞減的，所以我們只能保留單一元素。因此我們需要刪除長度為 4 的子數組，可以是 [5,4,3,2] 或 [4,3,2,1]。

範例 3：

• 輸入： arr = [1,2,3]
• 輸出： 0
• 解釋： 陣列已經是非遞減的。我們不需要刪除任何元素。

約束：

• 1 5
• 0 9

提示：

1. 關鍵是找出分別從第一個元素開始或以最後一個元素結束的最長非遞減子數組。
2. 刪除一些子數組後，結果是排序後的前綴和排序後綴的串聯，其中前綴的最後一個元素小於後綴的第一個元素。

解：

我們可以使用排序和二分搜尋技術。計劃如下：

方法：

1. 雙指標方法：

   • 首先，確定最長的非遞減前綴（左指標）。
   • 然後，找出最長的非遞減後綴（右指標）。
   • 之後，試著將這兩個子數組組合起來，考慮數組的中間部分，並調整要刪除的子數組，使組合後的數組不減。

2. 單調堆疊：

   • 使用單調堆疊來幫助以排序方式管理子數組元素。

3. 步驟：

   • 找出最長的非遞減前綴（左）。
   • 找出最長的非遞減後綴（右）。
   • 嘗試透過尋找可以形成有效組合的元素來合併兩個子數組。

4. 最佳化：

   • 使用二分搜尋來最佳化合併步驟，以找到要刪除的最小子陣列。

讓我們用 PHP 實作這個解：1574。要刪除以使數組排序的最短子數組

解釋：

1. 最長非遞減前綴與後綴:

   • 前綴是透過從頭開始遍歷數組直到元素按非遞減順序來決定的。
   • 同理，後綴也是從尾部開始遍歷確定的。

2. 初始最小移除：

   • 僅保留前綴或後綴來計算移除長度。

3. 合併字首和字尾:

   • 使用兩個指標（i 表示前綴，j 表示後綴）來找出要刪除的最小子數組，使得前綴的最後一個元素小於或等於後綴的第一個元素。

4. 回傳結果:

   • 結果是要刪除的子數組的最小長度，計算為初始刪除或前綴和後綴合併中較小的一個。

複雜

• 時間複雜度：O(n)，因為陣列最多遍歷兩次。
• 空間複雜度：O(1)，因為只使用了幾個變數。

此解決方案可以有效地找到要刪除的最短子數組，從而使用兩指標技術對數組進行排序，並且可以處理最多 10^5 個元素的約束的大型數組。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是要刪除以使數組排序的最短子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！