3555. 排序每个滑动窗口中最小的子数组 🔒
题目描述
给定一个整数数组 nums 和一个整数 k。
对于每个长度为 k 的连续 子数组，确定必须排序的连续段的最小长度，以便整个窗口成为 非递减 的；如果窗口已经排序，则其所需长度为零。
返回一个长度为 n − k + 1 的数组，其中每个元素对应其窗口的答案。
示例 1：
输入：nums = [1,3,2,4,5], k = 3
输出：[2,2,0]
解释：
nums[0...2] = [1, 3, 2]。排序[3, 2]得到[1, 2, 3]，答案是 2。nums[1...3] = [3, 2, 4]。排序[3, 2]得到[2, 3, 4]，答案是 2。nums[2...4] = [2, 4, 5]已经有序，所以答案是 0。
示例 2：
输入：nums = [5,4,3,2,1], k = 4
输出：[4,4]
解释：
nums[0...3] = [5, 4, 3, 2]。整个子数组必须有序，所以答案是4。nums[1...4] = [4, 3, 2, 1]。整个子数组必须有序，所以答案是4。
提示：
1 <= nums.length <= 10001 <= k <= nums.length1 <= nums[i] <= 106
解法
方法一：枚举 + 维护左侧最大值和右侧最小值
我们可以枚举每个长度为 $k$ 的子数组，对于每个子数组 $nums[i...i + k - 1]$，我们需要找到最小的连续段，使得排序后整个子数组都是非递减的。
对于子数组 $nums[i...i + k - 1]$，我们可以从左到右遍历数组，维护一个最大值 $mx$，如果当前值小于 $mx$，说明当前值不在正确的位置上，我们更新右边界 $r$ 为当前位置。同理，我们可以从右到左遍历数组，维护一个最小值 $mi$，如果当前值大于 $mi$，说明当前值不在正确的位置上，我们更新左边界 $l$ 为当前位置。在初始化时，我们将 $l$ 和 $r$ 都初始化为 $-1$，如果 $l$ 和 $r$ 都没有被更新，说明数组已经有序，返回 $0$，否则返回 $r - l + 1$。
时间复杂度 $O(n \times k)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。
Python3
class Solution:
def minSubarraySort(self, nums: List[int], k: int) -> List[int]:
def f(i: int, j: int) -> int:
mi, mx = inf, -inf
l = r = -1
for k in range(i, j + 1):
if mx > nums[k]:
r = k
else:
mx = nums[k]
p = j - k + i
if mi < nums[p]:
l = p
else:
mi = nums[p]
return 0 if r == -1 else r - l + 1
n = len(nums)
return [f(i, i + k - 1) for i in range(n - k + 1)]
Java
class Solution {
private int[] nums;
private final int inf = 1 << 30;
public int[] minSubarraySort(int[] nums, int k) {
this.nums = nums;
int n = nums.length;
int[] ans = new int[n - k + 1];
for (int i = 0; i < n - k + 1; ++i) {
ans[i] = f(i, i + k - 1);
}
return ans;
}
private int f(int i, int j) {
int mi = inf, mx = -inf;
int l = -1, r = -1;
for (int k = i; k <= j; ++k) {
if (nums[k] < mx) {
r = k;
} else {
mx = nums[k];
}
int p = j - k + i;
if (nums[p] > mi) {
l = p;
} else {
mi = nums[p];
}
}
return r == -1 ? 0 : r - l + 1;
}
}
C++
class Solution {
public:
vector<int> minSubarraySort(vector<int>& nums, int k) {
const int inf = 1 << 30;
int n = nums.size();
auto f = [&](int i, int j) -> int {
int mi = inf, mx = -inf;
int l = -1, r = -1;
for (int k = i; k <= j; ++k) {
if (nums[k] < mx) {
r = k;
} else {
mx = nums[k];
}
int p = j - k + i;
if (nums[p] > mi) {
l = p;
} else {
mi = nums[p];
}
}
return r == -1 ? 0 : r - l + 1;
};
vector<int> ans;
for (int i = 0; i < n - k + 1; ++i) {
ans.push_back(f(i, i + k - 1));
}
return ans;
}
};
Go
func minSubarraySort(nums []int, k int) []int {
const inf = 1 << 30
n := len(nums)
f := func(i, j int) int {
mi := inf
mx := -inf
l, r := -1, -1
for p := i; p <= j; p++ {
if nums[p] < mx {
r = p
} else {
mx = nums[p]
}
q := j - p + i
if nums[q] > mi {
l = q
} else {
mi = nums[q]
}
}
if r == -1 {
return 0
}
return r - l + 1
}
ans := make([]int, 0, n-k+1)
for i := 0; i <= n-k; i++ {
ans = append(ans, f(i, i+k-1))
}
return ans
}
TypeScript
function minSubarraySort(nums: number[], k: number): number[] {
const inf = Infinity;
const n = nums.length;
const f = (i: number, j: number): number => {
let mi = inf;
let mx = -inf;
let l = -1,
r = -1;
for (let p = i; p <= j; ++p) {
if (nums[p] < mx) {
r = p;
} else {
mx = nums[p];
}
const q = j - p + i;
if (nums[q] > mi) {
l = q;
} else {
mi = nums[q];
}
}
return r === -1 ? 0 : r - l + 1;
};
const ans: number[] = [];
for (let i = 0; i <= n - k; ++i) {
ans.push(f(i, i + k - 1));
}
return ans;
}