问题描述
一个序列 [b1,b2,...,bm] 若对于 2≤i≤m 满足 bi≤b1 ，则称为好序列。
现在给定 [a1,a2,...,an] ，求对于该序列的每一个后缀 [ak,ak+1,...,an](1≤k≤n)最少能划分成多少个好序列。
输入格式
第一行包含一个整数 n ，表示数组 a 的长度。
第二行包含 nn 个整数 a1,a2,a3,...,an，两两之间以一个空格分隔。
输出格式
输出 n 行，第 i 行输出 k=i时的答案。
样例输入
6
1 1 4 5 1 4
样例输出
3
3
2
1
2
1
样例解释
当 k=1 时， 可划分为： [[1,1],[4],[5,1,4]] 。
当 k=2 时， 可划分为： [[1],[4],[5,1,4]] 。
当 k=3 时， 可划分为： [[4],[5,1,4]] 。
当 k=4 时， 可划分为： [[5,1,4]] 。
当 k=5 时， 可划分为： [[1],[4]] 。
当 k=6 时， 可划分为： [[4]] 。
评测数据规模
对于所有评测数据， 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C | 2s | 256M |
解法代码
#include <stdio.h>
#include <stdlib.h>
#define N 1000010 // 定义数组的最大长度
int a[N], arr[N]; // a数组用于存储输入数据，arr数组用于存储结果
int stack[N]; // 使用数组来模拟栈，存储元素的索引
int stack_top = -1; // 栈顶指针，初始化为-1表示栈为空
int main()
{
int n = 0; // 定义变量n用于存储输入的元素个数
scanf("%d", &n); // 从标准输入读取元素个数
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);// 循环读取n个元素到数组a中
}
/*
* 从后往前遍历数组a，模拟deque的行为
* 对于每个元素，找到其右边第一个比它大的元素的索引，并计算距离（长度+1）
*/
for (int i = n - 1; i >= 0; i--)
{
// 弹出栈顶元素，直到栈为空或栈顶元素对应的值大于当前元素的值
while (stack_top >= 0 && a[stack[stack_top]] <= a[i])
{
stack_top--; // 栈顶指针下移，表示弹出栈顶元素
}
// 设置arr值
// 如果栈不为空，则arr[i]为栈顶索引+1（表示长度）+1（因为要从1开始计数，如果要从0开始则去掉一个+1）
// 如果栈为空，则arr[i]为1，表示当前元素右边没有比它大的元素
if (stack_top >= 0)
{
arr[i] = stack_top + 1 + 1; // 注意这里的+1+1，第一个+1是长度，第二个+1是因为从1开始计数
}
else
{
arr[i] = 1;
}
// 将当前元素的索引压入栈中
stack[++stack_top] = i; // 栈顶指针上移，并将当前元素的索引存入栈顶
}
/*
* 输出arr数组中的值
* 注意：此时arr数组中的索引对应的是原数组a中的索引（从0开始）
* 如果需要从1开始输出索引对应的值，可以在打印时做一个简单的调整（例如，打印arr[i] + 1）
* 但由于C语言习惯从0开始索引，这里直接输出即可
*/
for (int i = 0; i < n; i++) {
printf("%d\n", arr[i]); // 打印arr数组中的每个值
}
return 0;
}答案验证
