4109. 统计有效后缀排序的数量 II
难度困难
题目描述
给你两个整数数组 nums 和 target，长度分别为 n 和 m，其中 n <= m。
对于每个下标 i，考虑将原数组的 后缀 nums[i..n - 1] 按 非递增顺序 排序。
返回一个长度为 m - n + 1 的整数数组 ans，其中 ans[k] 表示使排序后的数组等于 target[k..k + n - 1] 的下标 i 的数量。
子数组 是数组中一个连续的 非空 元素序列。
数组的 后缀 是从任意下标开始并延伸至数组末尾的子数组。
示例 1：
输入： nums = [2,2,3], target = [2,2,3,2,1,3,2,2]
输出： [1,1,0,0,0,1]
解释：
分别对从下标 0、1 和 2 开始的后缀排序，会依次得到 [3, 2, 2]、[2, 3, 2] 和 [2, 2, 3]。
k = 0：选择i = 2可以得到[2, 2, 3]。k = 1：选择i = 1可以得到[2, 3, 2]。k = 2, 3, 4：均无法得到对应的子数组。k = 5：选择i = 0可以得到[3, 2, 2]。
因此，答案为 [1,1,0,0,0,1]。
示例 2：
输入： nums = [5,6,5], target = [5,6,5,5,6,5]
输出： [2,1,0,2]
解释：
对从下标 0 开始的后缀排序，会得到 [6, 5, 5]；对从下标 1 或 2 开始的后缀排序，都会得到 [5, 6, 5]。
k = 0：选择i = 1或i = 2可以得到[5, 6, 5]。k = 1：选择i = 0可以得到[6, 5, 5]。k = 2：无法得到[5, 5, 6]。k = 3：选择i = 1或i = 2可以得到[5, 6, 5]。
因此，答案为 [2, 1, 0, 2]。
提示：
n == nums.lengthm == target.length1 <= n <= m <= 1051 <= nums[i], target[i] <= 105
解法
方法一
1 | |
1 | |
1 | |
1 | |