What is the primary pattern for solving the 'Removing Minimum and Maximum From Array' problem?

The primary pattern is greedy choice combined with invariant validation. You calculate deletions for all possible approaches and select the one with the minimum deletions.

How do I handle edge cases in the 'Removing Minimum and Maximum From Array' problem?

Edge cases include arrays with only one element or arrays where the minimum and maximum are at the same position. Ensure you handle these efficiently to avoid errors.

What is the time complexity of the 'Removing Minimum and Maximum From Array' problem?

The time complexity is O(n), where n is the length of the array, since you need to find the positions of the minimum and maximum elements.

Can the solution be optimized further for space complexity?

Yes, the solution is already space-efficient with a space complexity of O(1), as it only requires a few variables to store indices.

What if I can only delete elements from one side of the array?

In such a case, you would need to adjust your approach to consider deletions from only the front or the back, which would change the solution's efficiency.

#2091

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

从数组中移除最大值和最小值

给你一个下标从 0 开始的数组 nums ，数组由若干互不相同的整数组成。 nums 中有一个值最小的元素和一个值最大的元素。分别称为最小值和最大值。你的目标是从数组中移除这两个元素。一次删除操作定义为从数组的前面移除一个元素或从数组的后面移除一个元素。返回将数组中最小值…

数组贪心

题目描述

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次删除操作定义为从数组的前面移除一个元素或从数组的后面移除一个元素。

返回将数组中最小值和最大值都移除需要的最小删除次数。

示例 1：

输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：

输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。

示例 3：

输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

提示：

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
nums 中的整数 互不相同

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        mi = mx = 0
        for i, num in enumerate(nums):
            if num < nums[mi]:
                mi = i
            if num > nums[mx]:
                mx = i
        if mi > mx:
            mi, mx = mx, mi
        return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate shows an understanding of greedy algorithms and how they apply to array manipulation.
question_mark
The candidate considers multiple approaches to minimize deletions and effectively handles edge cases.
question_mark
The candidate optimizes the solution for both time and space complexity while clearly explaining their approach.

warning

常见陷阱

外企场景

error
The candidate might overlook edge cases where the array only contains one element, or where the min and max elements are at the same position.
error
Failing to account for the scenario where deletions must come from both ends of the array could lead to suboptimal solutions.
error
Not validating the array’s size or handling out-of-bounds scenarios efficiently could result in runtime errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem could be modified to allow removing elements only from one side of the array (front or back).
arrow_right_alt
An extension of this problem could involve keeping track of the deleted elements in addition to the deletions themselves.
arrow_right_alt
A more complex variant might involve removing the minimum and maximum while ensuring the remaining elements maintain a specific order.

help

常见问题

外企场景

继续练习

#2087 网格图中机器人回家的最小代价 #2078 两栋颜色不同且距离最远的房子 #2071 你可以安排的最多任务数目