双端队列优化整数排序问题

双端队列在IT技术中是一种特殊的线性数据结构，它允许在两端进行插入和删除操作。在这个题目中，达达面临的是一个关于整数排序的问题，但使用双端队列作为主要工具。给定一个包含N个整数的序列，每个整数表示一个待处理的数值，达达需要按照从1到N的顺序处理这些数，且每次操作可以选择将当前数插入到现有双端队列的头部或尾部。 关键点在于如何利用双端队列的特性来优化排序过程。首先，达达将所有整数按升序排列，然后通过比较连续的元素来创建"缩点"（即相同的数值）。当遇到不同数值时，意味着达达需要一个新的双端队列来存储当前的数值。如果当前数值与前一个不同，或者这是第一个数，达达会创建一个新的队列并将当前数值放进去（队列初始化为单个元素）。 为了最小化双端队列的数量，达达需要确保在创建新队列时，总是选择具有最大索引的元素（`mx[i]`）作为新队列的起点，这样可以尽可能地复用已有队列。同时，她还需要记录队列的最小索引（`mi[i]`），以适应可能的队列合并操作。当队列的单调性（即连续元素的顺序）发生变化时，达达知道是时候创建一个新的队列，这由变量`b`来标记。 最后，`h`变量用于追踪当前活跃队列的最高索引，如果发现新队列的最高索引比`h`大，则表明需要创建新队列，反之则更新`h`。每当`b`变为`false`，表示单调性改变，`ans`加一，表示需要增加一个新队列。整个算法的核心目标是在满足处理要求的同时，最小化双端队列的数量。 因此，对于给定的输入样例： ```c++ 6 3 6 0 9 6 3 ``` 通过执行上述算法，达达将得到两个队列：第一个队列包含0、3和3，第二个队列包含6、6和9。由于所有数值都被处理过，而且没有创建多余的新队列，所以输出结果是2，表示最少需要2个双端队列来完成排序任务。