class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& arr) {
}
};
1574. 删除最短的子数组使剩余数组有序
给你一个整数数组 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^50 <= arr[i] <= 10^9原站题解
python3 解法, 执行用时: 68 ms, 内存消耗: 30 MB, 提交时间: 2023-03-25 10:06:45
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
right = n - 1
while right and arr[right - 1] <= arr[right]:
right -= 1
if right == 0: # arr 已经是非递减数组
return 0
# 此时 arr[right-1] > arr[right]
ans = right # 删除 arr[:right]
left = 0
while True: # 枚举 right
while right == n or arr[left] <= arr[right]:
ans = min(ans, right - left - 1) # 删除 arr[left+1:right]
if arr[left] > arr[left + 1]:
return ans
left += 1
right += 1
java 解法, 执行用时: 2 ms, 内存消耗: 57.5 MB, 提交时间: 2023-03-25 09:55:17
class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
int n = arr.length, right = n - 1;
while (right > 0 && arr[right - 1] <= arr[right])
--right;
if (right == 0) return 0; // arr 已经是非递减数组
// 此时 arr[right-1] > arr[right]
int ans = right; // 删除 0 到 right-1
for (int left = 0; ; ++right) // 枚举 right
while (right == n || arr[left] <= arr[right]) {
// 中间 left+1 到 right-1 可以删除
ans = Math.min(ans, right - left - 1);
if (arr[left] > arr[left + 1]) return ans;
++left;
}
}
}
golang 解法, 执行用时: 96 ms, 内存消耗: 9 MB, 提交时间: 2023-03-25 09:54:57
func findLengthOfShortestSubarray(arr []int) int {
n := len(arr)
right := n - 1
for right > 0 && arr[right-1] <= arr[right] {
right--
}
if right == 0 { // arr 已经是非递减数组
return 0
}
// 此时 arr[right-1] > arr[right]
ans := right // 删除 arr[:right]
for left := 0; ; right++ { // 枚举 right
for right == n || arr[left] <= arr[right] {
ans = min(ans, right-left-1) // 删除 arr[left+1:right]
if arr[left] > arr[left+1] {
return ans
}
left++
}
}
}
func min(a, b int) int { if a > b { return b }; return a }
cpp 解法, 执行用时: 100 ms, 内存消耗: 65.2 MB, 提交时间: 2023-03-25 09:54:39
class Solution {
public:
int findLengthOfShortestSubarray(vector<int> &arr) {
int n = arr.size(), right = n - 1;
while (right && arr[right - 1] <= arr[right])
--right;
if (right == 0) return 0; // arr 已经是非递减数组
// 此时 arr[right-1] > arr[right]
int ans = right; // 删除 0 到 right-1
for (int left = 0; ; ++right) // 枚举 right
while (right == n || arr[left] <= arr[right]) {
// 中间 left+1 到 right-1 可以删除
ans = min(ans, right - left - 1);
if (arr[left] > arr[left + 1]) return ans;
++left;
}
}
};
cpp 解法, 执行用时: 84 ms, 内存消耗: 65.2 MB, 提交时间: 2023-03-25 09:54:20
class Solution {
public:
int findLengthOfShortestSubarray(vector<int> &arr) {
int n = arr.size(), right = n - 1;
while (right && arr[right - 1] <= arr[right])
--right;
if (right == 0) return 0; // arr 已经是非递减数组
// 此时 arr[right-1] > arr[right]
int ans = right; // 删除 0 到 right-1
for (int left = 0; left == 0 || arr[left - 1] <= arr[left]; ++left) {
while (right < n && arr[right] < arr[left])
++right;
// 此时 arr[left] <= arr[right]，从 left+1 到 right-1 可以删除
ans = min(ans, right - left - 1);
}
return ans;
}
};
golang 解法, 执行用时: 92 ms, 内存消耗: 8.6 MB, 提交时间: 2023-03-25 09:53:50
func findLengthOfShortestSubarray(arr []int) int {
n := len(arr)
right := n - 1
for right > 0 && arr[right-1] <= arr[right] {
right--
}
if right == 0 { // arr 已经是非递减数组
return 0
}
// 此时 arr[right-1] > arr[right]
ans := right // 删除 arr[:right]
for left := 0; left == 0 || arr[left-1] <= arr[left]; left++ {
for right < n && arr[right] < arr[left] {
right++
}
ans = min(ans, right-left-1) // 删除 arr[left+1:right]
}
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
java 解法, 执行用时: 2 ms, 内存消耗: 57.9 MB, 提交时间: 2023-03-25 09:53:21
class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
int n = arr.length, right = n - 1;
while (right > 0 && arr[right - 1] <= arr[right])
--right;
if (right == 0) return 0; // arr 已经是非递减数组
// 此时 arr[right-1] > arr[right]
int ans = right; // 删除 0 到 right-1
for (int left = 0; left == 0 || arr[left - 1] <= arr[left]; ++left) {
while (right < n && arr[right] < arr[left])
++right;
// 此时 arr[left] <= arr[right]，从 left+1 到 right-1 可以删除
ans = Math.min(ans, right - left - 1);
}
return ans;
}
}
python3 解法, 执行用时: 68 ms, 内存消耗: 28.9 MB, 提交时间: 2023-03-25 09:02:59
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
right = n - 1
while right and arr[right - 1] <= arr[right]:
right -= 1
if right == 0: # arr 已经是非递减数组
return 0
# 此时 arr[right-1] > arr[right]
ans = right # 删除 arr[:right]
left = 0 # 枚举 left
while left == 0 or arr[left - 1] <= arr[left]:
while right < n and arr[right] < arr[left]:
right += 1
# 此时 arr[left] <= arr[right]，删除 arr[left+1:right]
ans = min(ans, right - left - 1)
left += 1
return ans