rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-12-22 09:36:05

impl Solution {
    pub fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut suf = vec![0; n];
        let mut g = Vec::new();
        for (i, &x) in nums.iter().enumerate().rev() {
            let j = g.partition_point(|&v| v < x);
            if j == g.len() {
                g.push(x);
            } else {
                g[j] = x;
            }
            suf[i] = j + 1; // 从 nums[i] 开始的最长严格递减子序列的长度
        }

        let mut mx = 0;
        g.clear();
        for (i, &x) in nums.iter().enumerate() {
            let j = g.partition_point(|&v| v < x);
            if j == g.len() {
                g.push(x);
            } else {
                g[j] = x;
            }
            let pre = j + 1; // 在 nums[i] 结束的最长严格递增子序列的长度
            if pre >= 2 && suf[i] >= 2 {
                mx = mx.max(pre + suf[i] - 1); // 减去重复的 nums[i]
            }
        }
        (n - mx) as i32
    }
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 43.8 MB, 提交时间: 2023-12-22 09:35:45

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumMountainRemovals = function (nums) {
    const n = nums.length;
    const suf = Array(n).fill(0);
    const g = [];
    for (let i = n - 1; i > 0; i--) {
        const x = nums[i];
        const j = lowerBound(g, x);
        if (j === g.length) {
            g.push(x);
        } else {
            g[j] = x;
        }
        suf[i] = j + 1; // 从 nums[i] 开始的最长严格递减子序列的长度
    }

    let mx = 0;
    g.length = 0;
    for (let i = 0; i < n - 1; i++) {
        const x = nums[i];
        const j = lowerBound(g, x);
        if (j === g.length) {
            g.push(x);
        } else {
            g[j] = x;
        }
        const pre = j + 1; // 在 nums[i] 结束的最长严格递增子序列的长度
        if (pre >= 2 && suf[i] >= 2) {
            mx = Math.max(mx, pre + suf[i] - 1); // 减去重复的 nums[i]
        }
    }
    return n - mx;
};

// 请看 https://www.bilibili.com/video/BV1AP41137w7/
var lowerBound = function (nums, target) {
    let left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < target) {
            left = mid; // 范围缩小到 (mid, right)
        } else {
            right = mid; // 范围缩小到 (left, mid)
        }
    }
    return right; // 或者 left+1
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 12.2 MB, 提交时间: 2023-12-22 09:35:28

class Solution {
public:
    int minimumMountainRemovals(vector<int> &nums) {
        int n = nums.size();
        vector<int> suf(n), g;
        for (int i = n - 1; i; i--) {
            int x = nums[i];
            auto it = lower_bound(g.begin(), g.end(), x);
            suf[i] = it - g.begin() + 1; // 从 nums[i] 开始的最长严格递减子序列的长度
            if (it == g.end()) {
                g.push_back(x);
            } else {
                *it = x;
            }
        }

        int mx = 0;
        g.clear();
        for (int i = 0; i < n - 1; i++) {
            int x = nums[i];
            auto it = lower_bound(g.begin(), g.end(), x);
            int pre = it - g.begin() + 1; // 在 nums[i] 结束的最长严格递增子序列的长度
            if (it == g.end()) {
                g.push_back(x);
            } else {
                *it = x;
            }
            if (pre >= 2 && suf[i] >= 2) {
                mx = max(mx, pre + suf[i] - 1); // 减去重复的 nums[i]
            }
        }
        return n - mx;
    }
};

golang 解法, 执行用时: 0 ms, 内存消耗: 5.1 MB, 提交时间: 2023-12-22 09:35:12

func minimumMountainRemovals(nums []int) int {
    n := len(nums)
    suf := make([]int, n)
    g := []int{}
    for i := n - 1; i > 0; i-- {
        x := nums[i]
        j := sort.SearchInts(g, x)
        if j == len(g) {
            g = append(g, x)
        } else {
            g[j] = x
        }
        suf[i] = j + 1 // 从 nums[i] 开始的最长严格递减子序列的长度
    }

    mx := 0
    g = g[:0]
    for i, x := range nums {
        j := sort.SearchInts(g, x)
        if j == len(g) {
            g = append(g, x)
        } else {
            g[j] = x
        }
        pre := j + 1 // 在 nums[i] 结束的最长严格递增子序列的长度
        if pre >= 2 && suf[i] >= 2 {
            mx = max(mx, pre+suf[i]-1) // 减去重复的 nums[i]
        }
    }
    return n - mx
}

java 解法, 执行用时: 12 ms, 内存消耗: 43.2 MB, 提交时间: 2023-12-22 09:34:50

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] suf = new int[n];
        List<Integer> g = new ArrayList<>();
        for (int i = n - 1; i > 0; i--) {
            int x = nums[i];
            int j = lowerBound(g, x);
            if (j == g.size()) {
                g.add(x);
            } else {
                g.set(j, x);
            }
            suf[i] = j + 1; // 从 nums[i] 开始的最长严格递减子序列的长度
        }

        int mx = 0;
        g.clear();
        for (int i = 0; i < n - 1; i++) {
            int x = nums[i];
            int j = lowerBound(g, x);
            if (j == g.size()) {
                g.add(x);
            } else {
                g.set(j, x);
            }
            int pre = j + 1; // 在 nums[i] 结束的最长严格递增子序列的长度
            if (pre >= 2 && suf[i] >= 2) {
                mx = Math.max(mx, pre + suf[i] - 1); // 减去重复的 nums[i]
            }
        }
        return n - mx;
    }

    // 请看 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(List<Integer> g, int target) {
        int left = -1, right = g.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (g.get(mid) < target) {
                left = mid; // 范围缩小到 (mid, right)
            } else {
                right = mid; // 范围缩小到 (left, mid)
            }
        }
        return right; // 或者 left+1
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 17 MB, 提交时间: 2023-12-22 09:34:15

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        def lis(nums: List[int]) -> List[int]:
            res = [0] * n
            g = []
            for i, x in enumerate(nums):
                j = bisect_left(g, x)
                if j == len(g):
                    g.append(x)
                else:
                    g[j] = x
                res[i] = j + 1
            return res
        pre = lis(nums)
        suf = lis(nums[::-1])[::-1]
        return n - max(p + s for p, s in zip(pre, suf) if p >= 2 and s >= 2) + 1  # -1 提到外面

python3 解法, 执行用时: 64 ms, 内存消耗: 17.1 MB, 提交时间: 2023-12-22 09:33:55

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        g = []
        for i in range(n - 1, 0, -1):
            x = nums[i]
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
            suf[i] = j + 1  # 从 nums[i] 开始的最长严格递减子序列的长度

        mx = 0  # 最长山形子序列的长度
        g = []
        for i, x in enumerate(nums):
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
            pre = j + 1  # 在 nums[i] 结束的最长严格递增子序列的长度
            if pre >= 2 and suf[i] >= 2:
                mx = max(mx, pre + suf[i] - 1)  # 减去重复的 nums[i]
        return n - mx

java 解法, 执行用时: 40 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-27 10:29:17

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;

        // asc[i] 表示数组 nums[0,i] 以 nums[i] 结尾最长递增子序列长度
        int[] asc = new int[n];
        for (int l = 0; l < n; l++) {
            int max = 1;
            for (int t = 0; t < l; t++) {
                if (nums[t] < nums[l]) {
                    max = Math.max(max, asc[t] + 1);
                }
            }
            asc[l] = max;
        }

        // desc[i] 表示数组 nums[i, n-1] 以 nums[i] 开始最长递减子序列长度
        int[] desc = new int[n];
        for (int r = n - 1; r >= 0; r--) {
            int max = 1;
            for (int t = n - 1; t > r; t--) {
                if (nums[r] > nums[t]) {
                    max = Math.max(max, desc[t] + 1);
                }
            }
            desc[r] = max;
        }

        int ans = n;
        for (int i = 1; i < n - 1; i++) {
            if (asc[i] > 1 && desc[i] > 1) {
                // asc[i] + desc[i] - 1 表示以 nums[i] 为山形数组的顶点，山形数组的最大长度
                ans = Math.min(ans, n - (asc[i] + desc[i] - 1));
            }
        }
        return ans;
    }
}

java 解法, 执行用时: 11 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-27 10:29:06

class Solution {
    // 找到 arr 中第一个大于等于 target 元素的下标（如果求非下降子序列，则要用 bisectRight）。
    public static int bisectLeft(List<Integer> arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        int index = arr.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < target)
                left = mid + 1;
            else {
                index = mid;
                right = mid - 1;
            }
        }
        return index;
    }

    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        // 左起区间的最长上升子序列长度，left[i] 表示以下标 i 结尾的最长上升子序列长度。
        int[] left = new int[n];
        // 二分查找求最长上升子序列。
        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 找到 arr 中大于等于 nums[i] 的第一个元素下标（找不到就直接插入，找到了则替换）。
            int index = bisectLeft(arr, nums[i]);
            if (index == arr.size())
                arr.add(nums[i]);
            else
                arr.set(index, nums[i]);
            // 两种情况最长上升子序列都是 index + 1。
            left[i] = index + 1;
        }
        arr.clear();
        // 右起区间的最长上升子序列长度（right[i] 为从末尾开始到 i 为止的最长上升子序列）。
        int[] right = new int[n];
        // 求法和上述方法相同。
        for (int i = n - 1; i >= 0; i--) {
            int index = bisectLeft(arr, nums[i]);
            if (index == arr.size())
                arr.add(nums[i]);
            else
                arr.set(index, nums[i]);
            right[i] = index + 1;
        }
        // 计算以下标 i 向左右扩展可以得到的最长山脉数组（将两端的最长上升子序列拼接起来）。
        int res = 0;
        for (int i = 0; i < n; i++)
            // 按照题目要求，不能以山顶作为开头或者结尾，所以要保证两端的上升子序列长度都要大于等于 2。
            if (left[i] >= 2 && right[i] >= 2)
                res = Math.max(res, left[i] + right[i] - 1);
        // 剩下的就是要去掉的最小长度。
        return n - res;
    }
}

golang 解法, 执行用时: 296 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-27 10:27:47

func minimumMountainRemovals(nums []int) int {
    res := len(nums)
    for i := 1; i < len(nums) - 1; i ++ {
        target := nums[i]
        inc := countInc(nums[:i], target) // 前半段需要删除的数量

        if inc >= i {
            continue
        }

        dec := countDec(nums[i + 1:], target) // 后半段需要删除的数量

        if dec + i >= len(nums) - 1 {
            continue
        }

        //fmt.Println(i, nums[i], inc, dec)

        res = min(res, inc + dec)
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func countDec(nums []int, target int) int {
    stack := []int{}
    for i := len(nums) - 1; i >= 0; i -- {
        num := nums[i]

        if num >= target {
            continue
        }

        l := 0
        for r := len(stack); l < r; {
            mid := (l + r) / 2
            if stack[mid] >= num {
                r = mid
            } else {
                l = mid + 1
            }
        }
        if l == len(stack) {
            stack = append(stack, num)
        } else {
            stack[l] = num
        }
    }
    return len(nums) - len(stack)
}

func countInc(nums []int, target int) int {
    // 计算以target为最大值的最长递增子序列，用dp
    // 单调栈只能计算连续的

    stack := []int{}
    for _, num := range nums {

        if num >= target {
            continue
        }

        l := 0
        for r := len(stack); l < r; {
            mid := (l + r) / 2
            if stack[mid] >= num {
                r = mid
            } else {
                l = mid + 1
            }
        }
        if l == len(stack) {
            stack = append(stack, num)
        } else {
            stack[l] = num
        }
    }
    return len(nums) - len(stack)
}

python3 解法, 执行用时: 2980 ms, 内存消耗: 20.5 MB, 提交时间: 2023-09-27 10:19:12

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        # 求两个单调子序列的最大和
        n = len(nums)
        
        @cache
        def dfs_up(i):
            res = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    res = max(dfs_up(j), res)
            return res + 1
        
        @cache
        def dfs_down(i):
            res = 0
            for j in range(n - 1, i, -1):
                if nums[j] < nums[i]:
                    res = max(dfs_down(j), res)
            return res + 1
        
        ans = 0
        for i in range(1, n - 1):
            if dfs_up(i) > 1 and dfs_down(i) > 1:  # 保证是山顶
                ans = max(dfs_up(i) + dfs_down(i) - 1, ans)
        return n - ans

python3 解法, 执行用时: 64 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-27 10:18:32

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        ans = []
        g = [] #长度为i的序列的最小障碍
        for x in obstacles:
            j = bisect_left(g, x) #此处与1964略微不同，相等是不合法的
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
            ans.append(j+1)
        return ans
    
    def minimumMountainRemovals(self, nums: List[int]) -> int:
       #从前到后找最长的，从后到前找最长的。比对两个结果，相加最长的即所需要删除的最短
        l = self.longestObstacleCourseAtEachPosition(nums)
        r = self.longestObstacleCourseAtEachPosition(nums[::-1])
        r = r[::-1]
        cur_max = 0
        n = len(nums)
        for i in range(n):
            if l[i] + r[i] > cur_max and l[i] >=2 and r[i] >=2:#特殊情况，由题意，至少长度要为2，否则就是单调增/减
                cur_max = l[i]+r[i]
        return n- (cur_max-1)