1∼N 的排列中的连号区间计数问题 - 算法解析与优化

1∼N 的排列中的连号区间计数问题 - 算法解析与优化/n/n问题描述/n/n小明这些天一直在思考这样一个奇怪而有趣的问题：在 1∼N 的某个排列中有多少个连号区间呢？这里所说的连号区间的定义是：如果区间 [L,R] 里面的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的'连续'数列，则称这个区间连号区间。当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。/n/n输入格式/n/n第一行是一个正整数 N ，表示排列的规模。/n/n第二行是 N 个不同的数字 Pi ，表示这 N 个数字的某一排列。/n/n输出格式/n/n输出一个整数，表示不同连号区间的数目。/n/n数据范围/n/n1≤N≤10000 , 1≤Pi≤N/n/n输入样例1：/n/n4/n3 2 4 1/n/n输出样例1：/n/n7/n/n输入样例2：/n/n5/n3 4 2 5 1/n/n输出样例2：/n/n9/n/n样例解释/n/n第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]/n/n第二个用例中，有 9 个连号区间分别是： [1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]/n/n## 算法解析/n/n算法1/n/n(暴力枚举) $O(n^2)$ /n/n枚举所有区间，判断是否是连号区间。/n/n时间复杂度/n/n枚举区间需要 $O(n^2)$ 的时间复杂度，判断区间是否连号需要 $O(n/log n)$ 的时间复杂度，总时间复杂度为 $O(n^3/log n)$。/n/n算法2/n/n(前缀和) $O(n/log n)$ /n/n枚举区间的左端点 $L$，对于每个左端点，使用前缀和 $sum_i$ 计算出区间 $[L,R]$ 的最小值和最大值，判断区间是否连号。/n/n时间复杂度/n/n枚举左端点需要 $O(n)$ 的时间复杂度，对于每个左端点，计算区间的最小值和最大值需要 $O(/log n)$ 的时间复杂度，总时间复杂度为 $O(n/log n)$。/n/nC++ 代码/n/nc++/n#include <iostream>/n#include <algorithm>/nusing namespace std;/n/nconst int MAXN = 10005;/nint a[MAXN], sum[MAXN];/n/nint main() {/n int n, ans = 0;/n cin >> n;/n for (int i = 1; i <= n; i++) {/n cin >> a[i];/n sum[i] = sum[i - 1] + a[i];/n }/n for (int l = 1; l <= n; l++) {/n for (int r = l; r <= n; r++) {/n int min_val = min(a[l], a[r]), max_val = max(a[l], a[r]);/n if (max_val - min_val + 1 == r - l + 1) {/n ans++;/n }/n }/n }/n cout << ans << endl;/n return 0;/n}/n/n/n算法3/n/n(单调栈) $O(n)$ /n/n使用单调栈维护区间的最小值和最大值，对于每个右端点 $R$，将栈中所有比 $a_R$ 大的元素出栈并更新答案。/n/n时间复杂度/n/n枚举右端点需要 $O(n)$ 的时间复杂度，每个元素出栈入栈最多一次，总时间复杂度为 $O(n)$。/n/nC++ 代码/n/nc++/n#include <iostream>/n#include <algorithm>/n#include <stack>/nusing namespace std;/n/nconst int MAXN = 10005;/nint a[MAXN];/n/nint main() {/n int n, ans = 0;/n cin >> n;/n for (int i = 1; i <= n; i++) {/n cin >> a[i];/n }/n stack<int> s;/n for (int r = 1; r <= n; r++) {/n while (!s.empty() && a[s.top()] > a[r]) {/n s.pop();/n }/n s.push(r);/n if (!s.empty()) {/n ans += s.top() - s.empty();/n }/n }/n cout << ans << endl;/n return 0;/n}/n/n/n## 总结/n/n本文介绍了三种解决连号区间计数问题的算法，并分析了它们的复杂度。其中单调栈算法具有 $O(n)$ 的时间复杂度，是效率最高的算法。希望这篇文章能帮助你更好地理解和解决这个问题。/n