计算左侧和右侧至少大于K个元素的元素

banq
要计算左侧和右侧至少大于K个元素的元素，您可以使用以下方法：

暴力方法： 遍历数组中的每个元素，对于每个元素，分别计算其左侧和右侧大于K的元素数量。最后统计符合条件的元素数量。

def count_elements_greater_than_k(arr, K):
    n = len(arr)
    count = 0

    for i in range(n):
        left_count = sum(1 for x in arr[:i] if x > K)
        right_count = sum(1 for x in arr[i+1:] if x > K)

        if left_count + right_count >= K:
            count += 1

    return count

优化方法： 可以通过动态规划的方式来优化，减少左侧和右侧计数的时间复杂度。

def count_elements_greater_than_k_optimized(arr, K):
    n = len(arr)
    count = 0

    left_counts = [0] * n
    right_counts = [0] * n

    # 计算每个元素左侧大于K的元素数量
    for i in range(1, n):
        left_counts<i> = left_counts[i-1] + (arr[i-1] > K)

    # 计算每个元素右侧大于K的元素数量
    for i in range(n-2, -1, -1):
        right_counts<i> = right_counts[i+1] + (arr[i+1] > K)

    # 统计符合条件的元素数量
    for i in range(n):
        if left_counts<i> + right_counts<i> >= K:
            count += 1

    return count

复杂案例：
给定一个大小为n (1 <= n <= 10^5)的数组arr[]和一个正整数k，任务是计算数组中的所有索引i ( 1<= i < n) ，使得至少k i左边的元素和 i右边至少k 个元素，它们严格小于第 i 个索引处的值（即 arr）。

Input: arr = {1,3,6,5,2,1}, k = 2
Output: 2
Explanation: 用粗体标出的元素只是有效索引，arr = {2,3,6,5,2,3}

Input: arr = {2,2,2}, k = 3
Output: 0

解决方案：
这个想法是选择一些特定的数据结构来跟踪最大值。这样我们就可以检查当前索引i是否大于左侧的最大元素。我们来看看核心思想。

我们将使用最大堆数据结构并始终保持其大小为 k。对于任何索引i，我们将检查i处的当前值（即 arr）是否大于最大堆顶元素，这意味着i左侧必须至少有k 个元素小于当前值价值。如果当前值小于最大堆顶，那么我们必须删除最大堆顶并将当前元素插入堆中，因为这将帮助我们进一步减少最大值，从而在验证时帮助其他未来元素。我们将在left[]数组中跟踪此验证。

我们将从右到左执行上述相同操作，并在right[]数组中跟踪验证。

最后，我们将遍历两个数组并检查left == 1 或 true && right == 1 或 true那么这是有效的索引。因此，增加我们的count。

分步方法：

  • 初始化两个优先级队列maxH和maxH2来跟踪k 个最大元素，并为left[]和right[]索引创建向量。
  • 从左到右迭代数组，更新优先级队列并标记满足left[]条件的元素。
  • 从右向左迭代数组，更新第二个优先级队列并标记满足 right [] 条件的元素。
  • 计算两边满足条件（ left == 1 或 true && right == 1 或 true）的元素数量。
  • 返回计数作为结果。 

#include<bits/stdc++.h>
using namespace std;

int validElements(vector<int>& nums, int k) {

    //初始化两个优先队列，以跟踪最大的 k 个元素
    priority_queue<int> maxH, maxH2;

    int n = nums.size();
    vector<int> left(n), right(n);

    // Iterate over the array from left to right
    for(int i = 0; i < n; i++){
        if(maxH.size() < k){
            maxH.push(nums<i>);
        }
        else{
            if(maxH.top() < nums<i>) left<i> = 1;
            else{
                maxH.pop();
                maxH.push(nums<i>);
            }
        }
    }

    // Iterate over the array from right to left
    for(int i = n - 1; i >= 0; i--){
        if(maxH2.size() < k){
            maxH2.push(nums<i>);
        }
        else{
            if(maxH2.top() < nums<i>) right<i> = 1;
            else{
                maxH2.pop();
                maxH2.push(nums<i>);
            }
        }
    }

    //计算双方最大的 k 个元素的个数
    int count = 0;
    for(int i = 0; i < n; i++) if(left<i> && right<i>) count++;

    return count;
}

int main() {

    // input array and k
    vector<int> nums = {2,3,6,5,2,3};
    int k = 2;
    
    // Call the function and print the result
    cout << validElements(nums, k) << endl;
    return 0;
}