难度: Hard
我们定义 arr 是 山形数组 当且仅当它满足：
arr.length >= 3i （从 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 <= 10001 <= nums[i] <= 109nums 删除一些元素后一定能得到山形数组。运行时间: 62 ms
内存: 16.3 MB
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
g = []
mx = 0
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
if pre >= 2 and suf[i] >= 2:
mx = max(mx, pre + suf[i] - 1)
return n - mx
题解的思路是首先用动态规划的方法分别计算数组中每个元素作为山顶的左侧的最长递增子序列长度和右侧的最长递减子序列长度。使用二分搜索优化的方法，通过两个辅助数组（或列表）来存储左侧和右侧的最长递增子序列的长度。对于右侧，从右向左遍历数组，并利用二分搜索在维护的递增序列中找到合适的位置更新或添加元素，并记录每个位置的最长递增子序列长度。对于左侧，从左向右同样操作，并同时检查如果当前元素既有左侧也有右侧子序列，则尝试更新最大的山顶长度。最后，数组的长度减去最大的山顶长度即为需要删除的元素个数，从而得到最少的删除次数。
时间复杂度: O(n log n)
空间复杂度: O(n)
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) # 找到x在g中的位置
if j == len(g):
g.append(x) # 如果x比g中所有元素都大，添加到g末尾
else:
g[j] = x # 否则更新g中的元素以保持最小可能性
suf[i] = j + 1 # 记录长度
g = [] # 重置g用于左侧递增序列
mx = 0 # 记录最大的山顶长度
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 # 记录当前位置的最长递增序列长度
if pre >= 2 and suf[i] >= 2: # 确保左右两侧都至少有两个元素
mx = max(mx, pre + suf[i] - 1) # 更新最大山顶长度
return n - mx # 返回最少删除次数
动态规划通常用于计算最长递增子序列（LIS）的问题，因为它可以有效地处理相关子问题并存储结果，避免重复计算。在本题中，动态规划用于确定数组中每个元素作为山顶的左侧最长递增子序列和右侧最长递减子序列的长度。然而，传统的动态规划解决LIS问题的时间复杂度为O(n^2)，这在元素数量较大时可能效率不高。为了优化这一过程，引入了二分搜索。二分搜索用于在已排序的列表中快速定位元素，将元素插入或更新到LIS中，这种方法将单次操作的时间复杂度降低到O(log n)。结合动态规划和二分搜索不仅保持了计算的准确性，还显著提高了算法的效率，使整体时间复杂度降至O(n log n)。
辅助数组是用于存储每个位置的最长递增子序列长度的简单且有效的数据结构。使用数组可以直接通过索引访问任何位置的信息，这在动态规划中是非常有用的，因为我们需要快速获取和更新前一个元素对应的序列长度。此外，数组在空间上连续，访问效率高，且实现简单。其他数据结构如链表或树状数组虽然在某些情况下也可用，但在本问题中，它们要么增加了实现的复杂性，要么在访问和更新操作中效率不如使用数组。
虽然二分搜索可以有效地找到元素的插入位置，但它依赖于数组已经被排序，这意味着每次插入或更新元素后，都必须保持数组的有序性。如果在一个很大的数组中频繁地插入和删除操作，尤其是在数组的前端进行这些操作，可能会导致效率低下，因为数组元素需要频繁移动以维持顺序。此外，二分搜索假设所有输入都符合预期（如无重复值等），如果输入数据不符合预期或存在异常值，可能导致查找失败或不准确。
为了确保每个元素作为山顶的左侧和右侧序列长度准确无误，算法从两个方向分别进行计算。首先，从左至右遍历数组，使用动态规划和二分搜索计算并记录每个元素的左侧最长递增序列长度。然后，从右至左遍历数组，同样使用动态规划和二分搜索来计算每个元素的右侧最长递减序列长度。这种从两个方向的独立计算确保了数据的准确性和完整性。同时，通过维护两个分别的辅助数组（或列表），使得每个元素的左右序列数据可以被隔离存储和快速访问，此外，确保在计算过程中不会存在数据的互相干扰，保证了结果的正确性。