🔗 🔴 1671. Minimum Number of Removals to Make Mountain Array 1913

tags: `Biweekly Contest 40` `LIS` `前後綴分解`

題意

如果一個下標從 $0$ 開始的陣列 $arr$ 滿足以下條件，則稱為 山形陣列(Mountain Array) ：

$arr.length \geq 3$
存在某個索引 $i$ $i$ 滿足 $0 < i < arr.length - 1$ $0 < i < a rr . l e n g t h - 1$ 並且：
- $arr[0] < arr[1] < ... < arr[i - 1] < arr[i]$
- $arr[i] > arr[i + 1] > ... > arr[arr.length - 1]$

給定一個整數陣列 $nums$ ，返回使 $nums$ 成為 山形陣列(Mountain Array) 所需刪除的最少元素數量。

約束條件

$3 \leq nums.length \leq 1000$
$1 \leq nums[i] \leq 10^9$
保證可以從 $nums$ 中形成一個山形陣列

思路：前後綴分解

首先轉換問題，題目要求的是使 $nums$ 成為山形陣列所需刪除的最少元素數量，等價於求 $nums$ 中最長的山形子序列的長度 $max\_len$ ，然後用 $nums$ 的長度減去 $max\_len$ 即為答案。

而若 $nums[i]$ 是山形子序列的最大值，則 $nums[i]$ 必須同時滿足：

$nums[i]$ 左邊的元素嚴格遞增，換句話說， $nums[i]$ 是一個嚴格遞增子序列的結尾
$nums[i]$ 右邊的元素嚴格遞減，換句話說， $nums[i]$ 是一個嚴格遞減子序列的開頭

故可以將問題轉化為：

求以 $nums[i]$ 結尾的最長遞增子序列(LIS) 的長度 $pre[i]$
求以 $nums[i]$ 開頭的最長遞減子序列(LDS) 的長度 $suf[i]$
對於以 $i$ 為山頂的山形子序列，其長度為 $pre[i] + suf[i] - 1$ ，扣除重複計算的山頂 $nums[i]$ 本身。
最後，在所有可能的山頂中，找出最長的山形子序列長度 $max\_len$ ，此時可以得到最少需要刪除的元素數量 $n - max\_len$ 。

此外，求以 $nums[i]$ 開頭的 LDS 等價於對反轉後的 $nums$ 後求 LIS，但需要把結果再反轉回來。

方法一：動態規劃(Dynamic Programming)

首先定義問題，由於求以 $nums[i]$ 開頭的 LDS 等價於對反轉後的 $nums$ 後求 LIS，因此這裡只做如何求 LIS 的說明。

令 $pre[i]$ 表示以 $nums[i]$ 結尾的最長遞增子序列的長度，則對於 $i$ 我們可以考慮 $nums[i]$ 前面的所有位置 $j$ （ $0 \leq j < i$ ），如果 $nums[j] < nums[i]$ ，則可以將 $nums[i]$ 接在 $nums[j]$ 後面，從而更新 $pre[i]$ 的值。

故可以得到以下遞迴式：

$pre[i] = \displaystyle\max_{0 \leq j < i \text{ and } nums[j] < nums[i]}(pre[j] + 1)$

計算 LIS 的具體步驟如下：

從左到右遍歷 $nums$ ，對於每個元素 $nums[i]$ ，求以 $nums[i]$ 結尾的最長遞增子序列的長度 $pre[i]$
初始時，所有位置的 $pre[i]$ 都設為 1，因為每個元素本身就是一個長度為1的遞增子序列
對於每個位置 $i$ ，檢查之前所有位置 $j$ （ $0 \leq j < i$ ），如果 $nums[i] > nums[j]$ ，則可以將 $nums[i]$ 接在 $nums[j]$ 後面，從而更新 $pre[i]$ 的值。

對於 $suf[i]$ 的求法，可以將 $nums$ 反轉後求 LIS，然後再反轉回來。因此，對於山頂 $i$ ，可以得到其山形子序列的長度為 $pre[i] + suf[i] - 1$ ，之所以要扣除 $1$ 是因為山頂 $nums[i]$ 被計算了兩次。最後，在所有可能的山頂中找出最長的山形子序列長度 $max\_len$ ，此時可以得到最少需要刪除的元素數量 $n - max\_len$ ，即為答案。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ $O (n^{2})$ ，其中 $n$ $n$ 是 $nums$ $n u m s$ 的長度。
- 計算 LIS 和 LDS 時所需的狀態數量皆為 $\mathcal{O}(n)$ ，每個狀態需要枚舉最多 $\mathcal{O}(n)$ 個位置，因此總時間複雜度為 $\mathcal{O}(n^2)$ 。
空間複雜度： $\mathcal{O}(n)$ ，用於存儲 $pre$ 和 $suf$ 陣列。

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. Find LIS from left to right
        pre = [1] * n # pre[i] 表示以 nums[i] 結尾的 LIS 長度
        for i in range(1, n): # 枚舉所有位置 i
            for j in range(i): # 枚舉 i 前面的所有位置 j
                if nums[i] > nums[j]: # nums[i] 可以接在 nums[j] 後面
                    pre[i] = max(pre[i], pre[j] + 1)

        # 2. Find LDS from right to left
        suf = [1] * n # suf[i] 表示以 nums[i] 為開頭的 LDS 長度
        for i in range(n-2, -1, -1):
            for j in range(n-1, i, -1):
                if nums[i] > nums[j]: # nums[i] 可以接在 nums[j] 前面
                    suf[i] = max(suf[i], suf[j] + 1)
    
        # 3. Find the maximum length of mountain array
        max_len = 0
        for i in range(1, n-1): # 以 i 為山頂
            # 若 pre[i] == 1 或 suf[i] == 1 代表山頂前或後沒有比它小的數字，根據定義，不是山形陣列
            if pre[i] > 1 and suf[i] > 1:
                max_len = max(max_len, pre[i] + suf[i] - 1) # 扣除重複的山頂
        return n - max_len

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1), suf(n, 1);

        // 1. Find LIS from left to right
        for (int i = 1; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (nums[i] > nums[j])
                    pre[i] = max(pre[i], pre[j] + 1);

        // 2. Find LDS from right to left
        for (int i = n - 2; i >= 0; --i)
            for (int j = n - 1; j > i; --j)
                if (nums[i] > nums[j])
                    suf[i] = max(suf[i], suf[j] + 1);

        // 3. Find the maximum length of mountain array
        int max_len = 0;
        for (int i = 1; i < n - 1; ++i)
            if (pre[i] > 1 && suf[i] > 1)
                max_len = max(max_len, pre[i] + suf[i] - 1);
        return n - max_len;
    }
};

方法二：貪心(Greedy) + 二分搜尋(Binary Search)

透過貪心(Greedy) 策略結合二分搜尋(Binary Search) ，我們可以將求 LIS 和 LDS 的時間複雜度優化至 $\mathcal{O}(n \log n)$ 。

假設有一個長度為 $ln$ 的子序列，基於貪心策略，若末尾的值越小，後續的元素更有可能接在這個子序列後面，使得整體的 LIS 更長。因此我們可以維護一個的單調遞增陣列 $tail$ ，其中 $tail[i]$ 表示長度為 $i+1$ 的 LIS 的最後一個元素的最小值。

在遇到一個新的數字 $x$ 時，我們要考慮他可以接在哪個位置後面，使得整體的 LIS 更長。若原本存在一個長度為 $j + 1$ 的 LIS，其最後一個元素的最小值為 $tail[j]$ ，則若 $x \leq tail[j]$ ，則 $x$ 可以替代 $tail[j]$ ，並保持 $tail$ 陣列的單調遞增性。

因此可以利用二分搜尋找到第一個大於等於 $x$ 的元素位置 $j$ ，並更新 $tail[j]$ 為 $x$ 。但若 $j$ 等於 $tail$ 陣列的大小，則代表 $x$ 比 $tail$ 中的所有元素都大，此時將 $x$ 添加到 $tail$ 中。而此時，對於以 $nums[i]$ 結尾的 LIS 長度最多為 $j + 1$ 。

對於 $suf[i]$ 的求法，同樣可以將 $nums$ 反轉後求 LIS，然後再反轉回來即可。

同樣地，對於山頂 $i$ ，可以得到其山形子序列的長度為 $pre[i] + suf[i] - 1$ ，之所以要扣除 $1$ 是因為山頂 $nums[i]$ 被計算了兩次。最後，在所有可能的山頂中找出最長的山形子序列長度 $max\_len$ ，此時可以得到最少需要刪除的元素數量 $n - max\_len$ ，即為答案。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 是 $nums$ $n u m s$ 的長度。
- 計算 LIS 和 LDS 時皆需要考慮 $O(n)$ 個位置，每個位置都需要做一次二分搜尋來找到合適的插入位置，因此總時間複雜度為 $\mathcal{O}(n \log n)$ 。
空間複雜度： $\mathcal{O}(n)$ ，用於存儲 $pre$ 和 $suf$ 陣列。

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)

        # pre[i] 表示以 nums[i] 結尾的 LIS 長度
        pre = [-1] * n
        tail = [] # tail[i] 表示長度為 i+1 的 LIS 的最後一個元素的最小值
        for i, x in enumerate(nums):
            j = bisect_left(tail, x) # 找到第一個 >= x 的元素位置
            if j == len(tail): # 如果 x 比 tail 中的所有元素都大，則將 x 添加到 tail 中
                tail.append(x)
            else: # 否則，更新 tail[j] 為 x
                tail[j] = x
            pre[i] = j + 1

        # suf[i] 表示以 nums[i] 為開頭的 LDS 長度
        # 這裡其實就只是反向求 LIS 而已，也可以透過反轉 nums 後求 LIS，並把結果再反轉回來
        suf = [-1] * n
        head = [] # head[i] 表示長度為 i+1 的 LDS 的第一個元素的最小值
        for i in range(n - 1, -1, -1):
            x = nums[i]
            j = bisect_left(head, x)
            if j == len(head):
                head.append(x)
            else:
                head[j] = x
            suf[i] = j + 1

        max_len = 0
        for i in range(n):
            if pre[i] > 1 and suf[i] > 1:
                max_len = max(max_len, pre[i] + suf[i] - 1)
        return n - max_len

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1), suf(n, 1);

        function<vector<int>(vector<int>&)> LIS = [&](vector<int>& nums) {
            int n = nums.size();
            vector<int> tail; // tail[i] 表示長度為 i+1 的 LIS 的最後一個元素的最小值
            vector<int> f(n); // f[i] 表示以 nums[i] 結尾的 LIS 長度
            for (int i = 0; i < n; ++i) {
                int j = lower_bound(tail.begin(), tail.end(), nums[i]) - tail.begin();
                if (j == tail.size())
                    tail.push_back(nums[i]);
                else
                    tail[j] = nums[i];
                f[i] = j + 1;
            }
            return f;
        };

        pre = LIS(nums);
        reverse(nums.begin(), nums.end()); // 反轉 nums 求 LIS
        suf = LIS(nums);
        reverse(suf.begin(), suf.end()); // 反轉 suf 恢復原狀

        int max_len = 0;
        for (int i = 1; i < n - 1; ++i)
            if (pre[i] > 1 && suf[i] > 1)
                max_len = max(max_len, pre[i] + suf[i] - 1);
        return n - max_len;
    }
};