C++程序数组中的领导者

背景

在日常生活中，我们需要寻找领导者来指导我们前进。同样，当我们处理数组时，有时需要找到数组中的领导者。

领导者是指一个数组中的元素，它的值大于等于它右边的所有元素。例如，下面的数组中，元素7和6是领导者：

array = [4, 3, 7, 2, 6, 5]

解决方法

方法一：遍历数组

我们可以对数组进行遍历，对于每个元素，都判断它是否为领导者。如果是领导者，则输出它的值。

#include <iostream>

using namespace std;

void findLeaders(int array[], int size)
{
    for (int i = 0; i < size; i++) {
        int j;
        for (j = i + 1; j < size; j++) {
            if (array[i] < array[j]) {
                break;
            }
        }
        if (j == size) {
            cout << array[i] << " ";
        }
    }
}

int main()
{
    int array[] = {4, 3, 7, 2, 6, 5};
    int size = sizeof(array) / sizeof(array[0]);
    findLeaders(array, size);
    return 0;
}

上面的代码中，findLeaders函数用于找到数组中的领导者，并输出它们的值。该函数中，我们先对每个元素进行遍历，然后对于每个元素，再对它右边的元素进行遍历，如果存在元素大于它，说明它不是领导者，直接跳出循环。如果它右边的所有元素都小于等于它，说明它是领导者，输出它的值。

方法二：从右到左遍历数组

观察上面的遍历方法，我们会发现，每个元素都对它右边的所有元素进行了一次遍历。这样的话，时间复杂度就是O(n^2)，并不是很高效。那么，有没有更高效的方法呢？答案是肯定的。

我们可以从右到左遍历数组，同时维护一个变量max，表示右边元素的最大值。从数组的最后一个元素开始，如果当前的元素大于等于max，则它就是领导者。把它输出后，同时更新max的值。

#include <iostream>

using namespace std;

void findLeaders(int array[], int size)
{
    int max = array[size - 1];
    cout << max << " ";
    for (int i = size - 2; i >= 0; i--) {
        if (array[i] >= max) {
            cout << array[i] << " ";
            max = array[i];
        }
    }
}

int main()
{
    int array[] = {4, 3, 7, 2, 6, 5};
    int size = sizeof(array) / sizeof(array[0]);
    findLeaders(array, size);
    return 0;
}

上面的代码中，我们从数组的最后一个元素开始遍历，同时维护一个变量max，表示右边元素的最大值。如果当前的元素大于等于max，则它就是领导者。把它输出后，同时更新max的值。