找出数组中所有降序尾部子数组的头元素

本文主要是介绍找出数组中所有降序尾部子数组的头元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

已知有这么一个数组： {16, 17, 4, 3, 5, 2}，那么它的降序尾部子数组有：{17, 4, 3, 5, 2}，{5, 2}，{2}，所以这几个数组的头元素分别是17，5，2。

这个问题比较容易理解，首先可以想到的方法就是双重循环遍历：

class LeadersInArray {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) System.out.print(arr[i] + " ");}}public static void main(String[] args) {LeadersInArray lead = new LeadersInArray();int arr[] = new int[]{16, 17, 4, 3, 5, 2};int n = arr.length;lead.printLeaders(arr, n);}
}

该实现的时间复杂度为：O(n^2)。

另外一种想法就是：既然这个数组存在于尾部，那么我们直接从后往前遍历也是可以的，只要一直维持递增的效果就行了，所以这样可以大大降低时间复杂度，其为：O(n)

class LeadersInArray {void printLeaders(int arr[], int size) {int max_from_right =  arr[size-1];System.out.print(max_from_right + " ");for (int i = size-2; i >= 0; i--) {if (max_from_right < arr[i]) {           max_from_right = arr[i];System.out.print(max_from_right + " ");}}    }public static void main(String[] args) {LeadersInArray lead = new LeadersInArray();int arr[] = new int[]{16, 17, 4, 3, 5, 2};int n = arr.length;lead.printLeaders(arr, n);}
}

这篇关于找出数组中所有降序尾部子数组的头元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---