C++程序统计大于数组左侧所有元素且至少有K个右侧元素小于其的数组元素

在计算机科学中，面对算法问题是很正常的事情。其中，针对数组问题的算法需求也是经常出现的。本文就将介绍一种常见的数组算法问题，并通过C++程序来解决问题。

问题描述

给定一个大小为N的数组，对于其中的第i个元素来说，要求其满足以下条件：
1. 它大于数组左边所有的元素
2. 它有至少K个右边的元素小于它

我们的任务就是计算有多少个元素满足上述条件。

下面给出一个例子，以便更好地理解该问题：

int nums[] = {5, 4, 3, 2, 1};
int k = 2;
int result = 0;

for(int i = 0; i < 5; i++){
    bool flag = true;
    int cnt = 0;
    for(int j = i + 1; j < 5; j++){
        if(nums[j] < nums[i]){
            cnt++;
        }
    }
    if(cnt >= k){
        for(int j = 0; j < i; j++){
            if(nums[j] >= nums[i]){
                flag = false;
                break;
            }
        }
        if(flag){
            result++;
        }
    }
}

可以看到，针对该问题的求解过程，我们需要进行两个循环嵌套。外层循环用于遍历数组中所有元素，内层循环用于在当前元素的右边部分寻找满足条件的元素。

优化算法

以上的代码虽然能够得到正确的结果，但其时间复杂度为O(N^2)，在数据规模较大时将会变得非常耗时。因此，我们需要对其进行优化。

考虑在遍历数组时建立一个辅助数组B，其中B[i]代表数组中元素在i位置右侧小于等于其的元素个数。然后，我们从数组的最右端开始往左侧遍历，对于每个i位置的元素，如果其满足条件，则将结果加1，否则继续往左侧查找。

以此为基础，我们可以写出如下代码：

int nums[] = {5, 4, 3, 2, 1};
int k = 2;
int result = 0;

int b[5] = {0};
for(int i = 4; i >= 0; i--){
    int cnt = 0;
    for(int j = i + 1; j < 5; j++){
        if(nums[j] <= nums[i]){
            cnt += b[j];
        }
    }
    b[i] = cnt + 1;

    if(i >= k && b[i] - 1 >= k && nums[i] > nums[i - k]){
        result++;
    }
}

可以看到，通过辅助数组B的建立，我们可以在O(N)的时间复杂度内求解该问题，该算法比前一种暴力破解时间复杂度降低了一个数量级。

完整代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int nums[] = {5, 4, 3, 2, 1};
    int k = 2;
    int result = 0;

    int b[5] = {0};
    for(int i = 4; i >= 0; i--){
        int cnt = 0;
        for(int j = i + 1; j < 5; j++){
            if(nums[j] <= nums[i]){
                cnt += b[j];
            }
        }
        b[i] = cnt + 1;

        if(i >= k && b[i] - 1 >= k && nums[i] > nums[i - k]){
            result++;
        }
    }
    cout << "结果为：" << result << endl;

    return 0;
}