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

编写一个程序，打印出数组中的所有领导者。如果一个元素大于其右侧的所有元素，则它是领导者。最右边的元素总是领导者。例如，在数组{16，17，4，3，5，2}中，领导者是17、5和2。

让输入数组为arr[]，数组的大小为 size 。

方法1（简单）

使用两个循环。外部循环从0到size-1运行，并逐个从左到右选择所有元素。内部循环将选择的元素与其右侧的所有元素进行比较。如果所选元素大于其右侧的所有元素，则所选元素是领导者。

#include<iostream>
            using namespace std;
             
            /* C++ Function to print leaders in an array */
            void printLeaders(int arr[], int size)
            {
                for (int i = 0; i < size; i++)
                {
                    int j;
                    for (j = i+1; j < size; j++)
                    {
                        if (arr[i] <= arr[j])
                            break;
                    }   
                    if (j == size) // the loop didn't break
                        cout << arr[i] << " ";
                  }
            }
             
            /* Driver program to test above function */
            int main()
            {
                int arr[] = {16, 17, 4, 3, 5, 2};
                int n = sizeof(arr)/sizeof(arr[0]);
                printLeaders(arr, n);
                return 0;
            }

输出：

17 5 2

时间复杂度： O(n*n)

辅助空间： O(1)

因为使用了常量额外的空间。

方法2（从右边扫描）

在数组中从右到左扫描所有元素，并保持到目前为止的最大值。当最大值改变其值时，打印出它。
下面的图片是上述方法的干扰：

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

下面是上述方法的实现：

#include <iostream>
            using namespace std;
             
            /* C++ Function to print leaders in an array */
            void printLeaders(int arr[], int size)
            {
                int max_from_right = arr[size-1];
             
                /* Rightmost element is always leader */
                cout << max_from_right << " ";
                 
                for (int i = size-2; i >= 0; i--)
                {
                    if (max_from_right < arr[i])
                    {          
                        max_from_right = arr[i];
                        cout << max_from_right << " ";
                    }
                }
             
            /* Driver program to test above function */
            int main()
            {
                int arr[] = {16, 17, 4, 3, 5, 2};
                int n = sizeof(arr)/sizeof(arr[0]);
                printLeaders(arr, n);
                return 0;
            }   ```

输出：