What is the main approach to solving the 'Minimum Number of Removals to Make Mountain Array' problem?

The main approach involves maximizing the length of the mountain subsequence using dynamic programming and binary search, instead of focusing on removals directly.

What makes this problem 'hard' in LeetCode?

The challenge comes from efficiently applying dynamic programming combined with binary search to find the longest increasing and decreasing subsequences, while keeping the time complexity low.

What are the key pitfalls to avoid in this problem?

Common pitfalls include incorrect handling of the subsequence directions (increasing vs. decreasing) and inefficient computation of LIS/LDS without using binary search.

How does binary search improve the solution?

Binary search helps to efficiently find the correct positions for elements when calculating LIS and LDS, reducing the time complexity to O(N log N).

How can I optimize my solution for large arrays?

To optimize the solution for large arrays, use binary search when calculating LIS and LDS to ensure the time complexity remains manageable at O(N log N).

#1671

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

得到山形数组的最少删除次数

我们定义 arr 是山形数组当且仅当它满足： arr.length >= 3 存在某个下标 i （从 0 开始）满足 0 且： arr[0] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 给你整数数组 nums ，请你返回将 nums …

数组二分查找动态规划贪心

题目描述

我们定义 arr 是 山形数组 当且仅当它满足：

arr.length >= 3
存在某个下标 i （从 0 开始）满足 0 < i < arr.length - 1 且：
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums ，请你返回将 nums 变成 山形状数组 的最少删除次数。

示例 1：

输入：nums = [1,3,1]
输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。

示例 2：

输入：nums = [2,1,1,5,6,2,3,1]
输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。

提示：

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
题目保证 nums 删除一些元素后一定能得到山形数组。

lightbulb

解题思路

方法一：动态规划

本题可以转化为求最长上升子序列和最长下降子序列。

我们定义 $left[i]$ 表示以 $nums[i]$ 结尾的最长上升子序列的长度，定义 $right[i]$ 表示以 $nums[i]$ 开头的最长下降子序列的长度。

那么最终答案就是 $n - \max(left[i] + right[i] - 1)$ ，其中 $1 \leq i \leq n$ ，并且 $left[i] \gt 1$ 且 $right[i] \gt 1$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    left[i] = max(left[i], left[j] + 1)
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if nums[i] > nums[j]:
                    right[i] = max(right[i], right[j] + 1)
        return n - max(a + b - 1 for a, b in zip(left, right) if a > 1 and b > 1)

speed

复杂度分析

指标	值
时间	O(N \log N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of dynamic programming and binary search techniques.
question_mark
Evaluate how efficiently the candidate handles the transition between increasing and decreasing subsequences.
question_mark
Assess the candidate’s ability to optimize the solution using binary search to keep the time complexity manageable.

warning

常见陷阱

外企场景

error
Failing to correctly distinguish between strictly increasing and strictly decreasing subsequences.
error
Not optimizing the LIS and LDS computations using binary search, leading to higher time complexity.
error
Misunderstanding the problem by focusing on removals rather than maximizing the length of the mountain subsequence.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given a non-integer array, apply similar logic to find the maximum subsequence.
arrow_right_alt
Modify the problem to allow for a peak that doesn’t strictly increase or decrease.
arrow_right_alt
Alter the constraints by reducing the array size to test the efficiency of the solution.

help

常见问题

外企场景

继续练习

#2439 最小化数组中的最大值 #2560 打家劫舍 IV #2616 最小化数对的最大差值