给定一个整数 n,以及 n 个整数 a1, a2, ..., an。定义一个数列为「连续上升数列」,当且仅当该数列中任意相邻两项差均为 1,例如:1, 2, 4 和 4, 3, 2, 1 都不是连续上升数列,但 1, 2, 3, 4 是连续上升数列。现在你需要将 a1, a2, ..., an 中所有连续上升的子序列全部删除,求最后剩余数列的长度。输入:第一行一个整数 n,表示输入数列的长度 (1 < n < 10^5)。 第二行 n 个整数 a1, a2, ..., an,表示输入数列 (1 < ai < 10^6)。 输出:输出一个整数,表示最后剩余数列的长度。队列方法,c或c++
时间: 2024-01-16 16:03:49 浏览: 117
以下是C++代码实现双指针方法解决该问题:
```c++
#include <iostream>
using namespace std;
const int MAXN = 1e5+5;
int n, a[MAXN], ans;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int i = 1; // i为当前数列的起点
while(i <= n) {
int j = i + 1;
while(j <= n && a[j] == a[j-1] + 1) { // 找到当前连续上升子序列的终点
j++;
}
if(j - i <= 1) { // 当前子序列长度小于等于1,不需要删除
ans++;
}
i = j; // 更新起点
}
cout << ans << endl;
return 0;
}
```
算法思路:
对于任意一个连续上升子序列,它的起点是唯一的,而终点可以是任意一个大于起点的数。因此,我们可以用双指针i,j来表示当前连续上升子序列的起点和终点,遍历整个数列,如果当前数和前一个数不连续上升,则将i更新为j,即将当前数作为新的连续上升子序列的起点;否则,继续向后遍历,直到找到当前连续上升子序列的终点j。如果当前子序列长度小于等于1,即i和j相邻或者i和j之间只有一个数,则不需要删除,将其计入剩余数列的长度ans中。
时间复杂度为O(n)。
阅读全文