[Leetcode解題] 1574. Shortest Subarray to be Removed to Make Array Sorted

9 October 2026

medium array two-pointers

題目

1574. Shortest Subarray to be Removed to Make Array Sorted

給定整數陣列 arr，請移除一段連續子陣列，使剩下的元素按照原本順序形成非遞減陣列，並回傳最短的移除長度。

非遞減表示相鄰元素符合 arr[k] <= arr[k + 1]，允許相等。移除區間可以是空的，所以原本就排好序時，答案為 0。

題目限制：1 <= arr.length <= 10^5，0 <= arr[i] <= 10^9。

解題思路

1. 刪除中間一段，等於保留前綴與後綴

如果保留前綴 arr[0..i] 與後綴 arr[j..n-1]，被刪掉的就是兩者之間的 arr[i+1..j-1]：

[ 保留的前綴 ][ 刪除區間 ][ 保留的後綴 ]
           i             j

刪除長度為：

j - i - 1

剩下的陣列要非遞減，必須滿足三個條件：

保留的前綴本身非遞減。
保留的後綴本身非遞減。
若兩段都非空，交界必須符合 arr[i] <= arr[j]。

另外也可以只保留前綴，或只保留後綴，這兩種情況要一起考慮。

2. 找出最長的非遞減前綴與後綴

從左往右找出最長非遞減前綴的終點 left：

left = 0
while left + 1 < n and arr[left] <= arr[left + 1]:
    left += 1

若 left == n - 1，代表整個陣列已經非遞減，直接回傳 0。

接著從右往左找出最長非遞減後綴的起點 right：

right = n - 1
while right > 0 and arr[right - 1] <= arr[right]:
    right -= 1

任何合法的非空前綴都必須結束於 left 或更左邊；任何合法的非空後綴都必須開始於 right 或更右邊。超出這些邊界，就會保留一組原本逆序的相鄰元素。

3. 先考慮只保留其中一段

只保留最長非遞減前綴時，刪除 arr[left+1..n-1]，長度為 n - left - 1。

只保留最長非遞減後綴時，刪除 arr[0..right-1]，長度為 right。

因此可以先設定：

answer = min(n - left - 1, right)

這也涵蓋保留的前綴或後綴為空的情況。

4. 用雙指針尋找可以接起來的兩段

令 i = 0、j = right，分別指向前綴終點與後綴起點。

如果 arr[i] <= arr[j]，代表兩段可以接起來，更新答案：

answer = min(answer, j - i - 1)
i += 1

固定 i 時，越小的合法 j 會得到越短的刪除區間。既然目前已經找到最早可接上的 j，就改試更長的前綴，讓 i 向右移動。

如果 arr[i] > arr[j]，交界不合法，就讓 j 向右移動：

j += 1

後綴非遞減，往右才有機會遇到足夠大的值。

5. 為什麼 j 不需要回到 right？

前綴也是非遞減，所以 i 往右移動後，新的 arr[i] 只會更大或相等。

先前因為太小而被跳過的後綴元素，對新的 arr[i] 仍然太小。因此 j 可以繼續往右找，不必每次重新搜尋。

兩個指針都只往右移動，即使看起來在搜尋配對，總時間仍然是 $O(n)$。

範例追蹤

以題目第一個範例為例：

索引：  0  1  2   3  4  5  6  7
arr = [1, 2, 3, 10, 4, 2, 3, 5]

最長非遞減前綴是 [1, 2, 3, 10]，所以 left = 3。
最長非遞減後綴是 [2, 3, 5]，所以 right = 5。
只保留前綴要刪除 4 個元素，只保留後綴要刪除 5 個元素，因此 answer = 4。

從 i = 0、j = 5 開始：

i	j	比較	動作	answer
0	5	`1 <= 2`	可接合，刪除長度為 `4`；`i` 前進	4
1	5	`2 <= 2`	可接合，刪除長度為 `3`；`i` 前進	3
2	5	`3 > 2`	無法接合，`j` 前進	3
2	6	`3 <= 3`	可接合，刪除長度為 `3`；`i` 前進	3
3	6	`10 > 3`	無法接合，`j` 前進	3
3	7	`10 > 5`	無法接合，`j` 前進至陣列外	3

答案為 3。例如保留 arr[0..2] 與 arr[6..7]，刪除中間的 [10, 4, 2]，剩下 [1, 2, 3, 3, 5]。

演算法步驟

找出最長非遞減前綴的終點 left。若整個陣列已排序，回傳 0。
找出最長非遞減後綴的起點 right。
用只保留前綴或只保留後綴的刪除長度初始化答案。
設定 i = 0、j = right，在 i <= left 且 j < n 時搜尋。
若 arr[i] <= arr[j]，更新答案並移動 i；否則移動 j。
回傳答案。

C++ 實作

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();

        int left = 0;
        int right = n - 1;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            ++left;
        }

        if (left == n - 1) return 0;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            --right;
        }

        int answer = min(n - left - 1, right);
        int j = right;
        for (int i = 0; i <= left; ++i) {
            while (j < n && arr[i] > arr[j]) {
                ++j;
            }

            if (j == n) break;
            answer = min(answer, j - i - 1);
        }

        return answer;
    }
};

Python 實作

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left = 0
        right = n - 1
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1

        if left == n - 1:
            return 0

        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1

        answer = min(n - left - 1, right)
        j = right
        for i in range(left + 1):
            while j < n and arr[i] > arr[j]:
                j += 1

            if j == n:
                break
            answer = min(answer, j - i - 1)

        return answer