1671. 得到山形數(shù)組的最少刪除次數(shù)

【算法】【動態(tài)規(guī)劃、貪心、二分查找】力扣1671. 得到山形數(shù)組的最少刪除次數(shù)

問題描述

給定一個整數(shù)數(shù)組 nums ，我們定義該數(shù)組為山形數(shù)組當且僅當：

1. nums 的長度至少為 3。
2. 存在一個下標 i 滿足 0 < i < len(nums) - 1 且：
   • nums[0] < nums[1] < ... < nums[i - 1] < nums[i]
   • nums[i] > nums[i + 1] > ... > nums[len(nums) - 1]

現(xiàn)在，給定整數(shù)數(shù)組 nums，我們的目標是將其變?yōu)樯叫螖?shù)組，問最少刪除多少個元素。

問題解析

正難則反，我們可以反過來思考原本的nums數(shù)組中能組成的最長的山形數(shù)組的子序列的長度是多少，最后將數(shù)組長度減去這個最長子序列的長度，即為最少刪除個數(shù)。顯然，這是一個最長上升子序列問題。

示例

示例 1：

輸入：nums = [1,3,1]
輸出：0
解釋：數(shù)組本身就是山形數(shù)組，無需刪除元素。

示例 2：

輸入：nums = [2,1,1,5,6,2,3,1]
輸出：3
解釋：一種方法是刪除下標為 0、1 和 5 的元素，得到山形數(shù)組 [1,5,6,3,1]。

解法一：動態(tài)規(guī)劃

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        # suf[i] 為以i為起點的后綴最長嚴格下降子序列的長度
        suf = [1] * n
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if nums[j] < nums[i]:
                    suf[i] = max(suf[i], suf[j] + 1)
        
        mx = 0
        pre = [1] * n
        for i in range(0, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    pre[i] = max(pre[i], pre[j] + 1)
            if pre[i] >= 2 and suf[i] >= 2:
                mx = max(mx, pre[i] + suf[i] - 1)
        return n - mx

解法分析：

• 構建兩個數(shù)組 pre 和 suf，分別表示以每個元素為起點的最長上升和下降子序列的長度。
• 使用兩層嵌套循環(huán)更新 pre 和 suf 數(shù)組。
• 尋找滿足條件的元素，計算最大山形數(shù)組長度，最終返回刪除元素的個數(shù)。

復雜度分析：

• 時間復雜度：$O(n^2)$
• 空間復雜度：$O(n)$

解法二：貪心 + 二分

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        g = []  # g[i] 代表最長上升子序列長度為 i + 1 的最小元素
        for i in range(n - 1, 0, -1):
            x = nums[i]
            j = bisect_left(g, x)  # 尋找第一個 >= x 的元素的下標
            if j == len(g):  # 代表沒有 >= x 的元素
                g.append(x)  # 添加 x 到 g
            else:
                g[j] = x  # 更新最小元素
            suf[i] = j + 1  # j + 1 代表了這個序列的長度。

        mx = 0
        g = []
        pre = 0
        for i in range(0, n, 1):
            x = nums[i]
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
            pre = j + 1
            # 題目要求數(shù)組長度至少為3，
            # 也就是說，最簡單的山形數(shù)組的最大值在正中間，左右至少有一個元素
            # 能組成山形數(shù)組的子序列也要滿足這個要求
            # pre == 1代表左邊沒有元素，suf[i] == 1代表右邊沒有元素。
            if pre >= 2 and suf[i] >= 2:
                mx = max(mx, pre + suf[i] - 1)
        return len(nums) - mx

解法分析：

• 利用貪心思想，維護一個輔助數(shù)組 g，其中 g[i] 代表最長上升子序列長度為 i + 1 的最小元素。
• 使用二分查找更新 g 數(shù)組。
• 遍歷數(shù)組，計算最大山形數(shù)組長度，最終返回刪除元素的個數(shù)。

復雜度分析：

• 時間復雜度：$O(nlogn)$
• 空間復雜度：$O(n)$

總結

本文介紹了解決力扣1671題的兩種方法：動態(tài)規(guī)劃和貪心 + 二分。動態(tài)規(guī)劃方法通過構建兩個輔助數(shù)組，分別表示以每個元素為起點的最長上升和下降子序列的長度，然后遍歷數(shù)組尋找滿足條件的元素，計算最大山形數(shù)組長度。貪心 + 二分方法則利用貪心思想和二分查找，維護一個輔助數(shù)組，遍歷數(shù)組計算最大山形數(shù)組長度。兩種方法的時間復雜度分別為 O(n^2) 和 O(n log n)，空間復雜度均為 O(n)。在實際應用中，可以根據(jù)具體情況選擇適合的方法。文章來源地址http://www.zghlxwxcb.cn/news/detail-800287.html

到了這里，關于【算法】【Python3、動態(tài)規(guī)劃、貪心、二分查找】力扣1671. 得到山形數(shù)組的最少刪除次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！