炼金术师

题目链接：nowcoder 217127

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116243190

题目大意

给你一些操作，每次将 1~x 的地方染上一个新的颜色。
你可以任意选一个颜色，选一个 x 把 1~x 的地方都染上这个颜色。
问你你至少要染多少次才能染的跟题目的一样。

思路

根据题目容易看出它就是要你维护一个单调队列，然后问你到最后它的长度。

然后你就跟着做就好了。

代码

#include<cstdio>

using namespace std;

int n, x, q[1000001];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        while (q[0] && q[q[0]] <= x) q[0]--;
        q[++q[0]] = x;//维护单调队列
    }

    printf("%d", q[0]);//输出最后单调队列的长度

    return 0;
}