2519：统计 K-Big 索引的数量（★★）

力扣第 2519 题

题目

给定一个 下标从0开始 的整数数组 nums 和一个正整数 k 。

如果满足以下条件，我们称下标 i 为 k-big ：

• 存在至少 k 个不同的索引 idx1 ，满足 idx1 < i 且 nums[idx1] < nums[i] 。
• 存在至少 k 个不同的索引 idx2 ，满足 idx2 > i 且 nums[idx2] < nums[i] 。

返回 k-big 索引的数量。

示例 1 ：

输入：nums = [2,3,6,5,2,3], k = 2
输出：2
解释：在nums中只有两个 2-big 的索引:
- i = 2 --> 有两个有效的 idx1: 0 和 1。有三个有效的 idx2: 2、3 和 4。
- i = 3 --> 有两个有效的 idx1: 0 和 1。有两个有效的 idx2: 3 和 4。

示例 2 ：

输入：nums = [1,1,1], k = 3
输出：0
解释：在 nums 中没有 3-big 的索引

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= nums.length

相似问题：

• 0315：计算右侧小于当前元素的个数
• 2420：找到所有好下标（1695 分）

分析

• 有序集合模拟即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from sortedcontainers import SortedList
class Solution:
    def kBigIndices(self, nums: List[int], k: int) -> int:
        L,R = SortedList(),SortedList(nums)
        res = 0
        for i,x in enumerate(nums):
            R.remove(x)
            a = L.bisect_left(x)
            b = R.bisect_left(x)
            res += a>=k and b>=k
            L.add(x)
        return res

1040 ms