题目解析
在某个学校的趣味游戏活动中，N 名同学站成一排，他们的年龄恰好是 1 到 N ，需要注意的是他们并不是按照年龄的大小排列的，而是随机排列的。
游戏的规则是请同学们快速计算出，如果在这 N 名同学的小组中，取出所有区间长度 >=2 的包含连续数的区间，并求出每个区间中第 2 大的数，那么这些数的和最终是多少？
比如有 4 名同学，他们排好队之后，4 个人的年龄分别是 4 2 3 1。
如果取长度为 2 的区间可以取：(4,2） (2,3） (3,1)，这 3 个区间的次大数的和为 2 + 2 + 1 = 5。
如果取长度为 3 的区间可以取：(4,2,3) (2,3,1)，这 2 个区间的次大数的和为 3 + 2 =5。
如果取长度为 4 的区间可以取：(4,3,2,1)，这 1 个区间的次大数的和为 3。
因此，所有长度 >=2 的包含连续数的区间中的次大数的和为 5 + 5 + 3 = 13。
输入格式:
第一行一个整数 N。
第二行 N 个整数，这 N 个整数一定是数字 1~N 打乱次序后的结果。
输出格式:
输出一个整数，表示所有区间长度 >=2 的包含连续数的区间中第 2 大的数的和。
输入输出样例:
输入样例1
4
4 2 3 1
输出样例1
13
输入样例2
6
1 6 2 4 3 5
输出样例2
50
输入样例3
12
12 1 3 2 10 8 9 7 6 4 5 11
输出样例3
493
数据范围
对于 30% 的数据，保证 2<=n<=100。
对于 100% 的数据，保证 2<=n<=1000。
解题思路
大家一开始想的思路可能都是这样的暴力穷举法：
-
枚举所有可能的区间
[i, j]，(两两一组，三三一组....)，并计算每个区间的次大值。 -
时间复杂度为 O(N^3)，因为需要三层循环：外层循环确定起点
i，内层循环确定终点j，再对区间[i, j]进行排序以找到次大值。 -
这种方法在数据规模较大时会超时。
优化解法：
-
使用单次遍历的方式，动态维护当前区间的最大值和次大值。
-
具体来说就是遍历每一个开始点，获取这个开始点从2个数的区间到3个数的区间....一直到结束区间的最大值和次大值，这样可以保留最大值和次大值，避免像暴力穷举法中区间变大以后需要重新计算，减少了一层循环。
-
具体步骤如下：
-
遍历数组，从每个位置
i开始，向右扩展区间。 -
在扩展过程中，动态更新当前区间的最大值和次大值。
-
每次扩展后，将当前区间的次大值累加到结果中。
-
-
时间复杂度为 O(N^2)，因为我们只需要两层循环：外层循环确定起点
i，内层循环扩展终点j。
代码示例
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 输入学生人数int[] a = new int[n]; // 存储学生的年龄for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}long sum = 0; // 结果变量// 遍历所有可能的起点 ifor (int i = 0; i < n - 1; i++) {int maxVal = Math.max(a[i], a[i + 1]); // 当前区间的最大值int secondVal = Math.min(a[i], a[i + 1]); // 当前区间的次大值sum += secondVal; // 累加当前区间的次大值// 向右扩展区间for (int j = i + 2; j < n; j++) {if (a[j] > maxVal) { // 如果新元素比当前最大值大secondVal = maxVal; // 更新次大值maxVal = a[j]; // 更新最大值} else if (a[j] > secondVal) { // 如果新元素介于最大值和次大值之间secondVal = a[j]; // 更新次大值}sum += secondVal; // 累加当前区间的次大值}}System.out.println(sum); // 输出最终结果}
}样例分析
下面来分析一个简单的案例：
输入：
4 2 3 1
过程：
-
起点
i = 0，区间[4, 2]：- 最大值：4，次大值：2。
- 累加次大值：
sum = 2。
-
扩展到
j = 2，区间[4, 2, 3]：（区间慢慢变大）- 更新最大值为 4，次大值为 3。
- 累加次大值：
sum = 2 + 3 = 5。
-
扩展到
j = 3，区间[4, 2, 3, 1]：- 最大值仍为 4，次大值仍为 3。
- 累加次大值：
sum = 5 + 3 = 8。
-
起点
i = 1，区间[2, 3]：（遍历下一个节点）- 最大值：3，次大值：2。
- 累加次大值：
sum = 8 + 2 = 10。
-
扩展到
j = 3，区间[2, 3, 1]：- 最大值仍为 3，次大值为 2。
- 累加次大值：
sum = 10 + 2 = 12。
-
起点
i = 2，区间[3, 1]：- 最大值：3，次大值：1。
- 累加次大值：
sum = 12 + 1 = 13。
输出：
13
)