What is the key technique to solve the Shortest Subarray to be Removed to Make Array Sorted problem?

The key technique is binary search over the valid answer space, paired with two pointers to identify the longest non-decreasing subsequences.

How do I optimize the solution for large arrays in this problem?

Using binary search and two pointers helps optimize the solution, achieving a time complexity of O(N) while keeping space complexity to O(1).

What is the role of the monotonic stack in solving this problem?

The monotonic stack helps efficiently track the indices of the non-decreasing subarrays, making it easier to determine which subarray to remove.

Can the Shortest Subarray to be Removed to Make Array Sorted problem have multiple correct answers?

Yes, there can be multiple valid subarrays to remove, but the goal is to find the shortest one.

What is the time complexity of the optimal solution for this problem?

The time complexity is O(N), where N is the length of the array, due to the use of binary search and two-pointer techniques.

#1574

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

删除最短的子数组使剩余数组有序

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是非递减的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。示例 1：输入： arr = [1,2,3,10,4,2,3,5] 输出： 3 解释：我们需要删除的最短子…

数组双指针二分查找栈单调栈

题目描述

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。

一个子数组指的是原数组中连续的一个子序列。

请你返回满足题目要求的最短子数组的长度。

示例 1：

输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。

示例 2：

输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。

示例 3：

输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。

示例 4：

输入：arr = [1]
输出：0

提示：

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

lightbulb

解题思路

方法一：双指针 + 二分查找

我们先找出数组的最长非递减前缀和最长非递减后缀，分别记为 $\textit{nums}[0..i]$ 和 $\textit{nums}[j..n-1]$ 。

如果 $i \geq j$ ，说明数组本身就是非递减的，返回 $0$ 。

否则，我们可以选择删除右侧后缀，也可以选择删除左侧前缀，因此初始时答案为 $\min(n - i - 1, j)$ 。

接下来，我们枚举左侧前缀的最右端点 $l$ ，对于每个 $l$ ，我们可以通过二分查找，在 $\textit{nums}[j..n-1]$ 中找到第一个大于等于 $\textit{nums}[l]$ 的位置，记为 $r$ ，此时我们可以删除 $\textit{nums}[l+1..r-1]$ ，并且更新答案 $\textit{ans} = \min(\textit{ans}, r - l - 1)$ 。继续枚举 $l$ ，最终得到答案。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i + 1 < n and arr[i] <= arr[i + 1]:
            i += 1
        while j - 1 >= 0 and arr[j - 1] <= arr[j]:
            j -= 1
        if i >= j:
            return 0
        ans = min(n - i - 1, j)
        for l in range(i + 1):
            r = bisect_left(arr, arr[l], lo=j)
            ans = min(ans, r - l - 1)
        return ans

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Strong candidates will demonstrate proficiency with binary search and two-pointer techniques.
question_mark
Look for the ability to identify the key patterns in array manipulation and optimally apply them.
question_mark
Candidates should be able to explain how binary search can be used to reduce the search space effectively.

warning

常见陷阱

外企场景

error
Failing to optimize the solution by overlooking binary search, leading to unnecessary brute-force approaches.
error
Not recognizing the importance of non-decreasing subarrays from the beginning or end of the array.
error
Overcomplicating the problem with unnecessary data structures or inefficient algorithms.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem by allowing multiple subarrays to be removed.
arrow_right_alt
Introduce additional constraints, such as the array being sorted in descending order.
arrow_right_alt
Extend the problem to handle cases where the array contains negative numbers.

help

常见问题

外企场景

继续练习

#1793 好子数组的最大分数 #962 最大宽度坡 #2454 下一个更大元素 IV