单调队列size函数

### 单调队列的实现 单调队列是一种特殊的队列结构，其中存储的数据保持有序状态（通常是递增或递减）。通过利用 C++ STL 中的 `deque` 容器以及自定义逻辑，可以高效地实现这一功能。 以下是基于 C++ STL 的单调队列实现方法： #### 使用 `std::deque` 实现单调队列 下面是一个典型的单调队列实现示例代码，用于维护窗口内的最大值或最小值。此代码展示了如何使用 `std::deque` 来构建一个支持 O(1) 时间复杂度查询最值的操作。 ```cpp #include <iostream> #include <vector> #include <deque> using namespace std; // 维护滑动窗口的最大值 void slidingWindowMaximum(const vector<int>& nums, int k) { deque<int> dq; // 双端队列，用来保存索引 for (int i = 0; i < nums.size(); ++i) { // 移除超出当前窗口范围的元素 while (!dq.empty() && dq.front() < i - k + 1) { dq.pop_front(); } // 从队列尾部移除小于当前元素的所有值，以维持单调性 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } // 将当前元素加入队列 dq.push_back(i); // 输出窗口中的最大值 if (i >= k - 1) { cout << nums[dq.front()] << " "; } } } int main() { vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; slidingWindowMaximum(nums, k); return 0; } ``` 上述代码实现了在一个大小固定的滑动窗口中寻找每一步的最大值的功能[^1]。这里的关键在于双端队列 (`std::deque`) 被用来跟踪可能成为候选最大值的元素索引，并且始终保持这些索引对应的数值呈严格递减顺序。 #### 自定义比较函数的应用 如果需要改变默认行为（比如改为求解最小值），可以通过调整条件判断语句完成。例如，在上面的例子中修改 `nums[dq.back()] <= nums[i]` 成为 `nums[dq.back()] >= nums[i]` 则会得到相反的结果——即每次输出的是该区间内的最小值而非最大值[^2]。 另外需要注意的一点是在处理大量输入数据时性能考量方面的问题。尽管标准模板库提供了丰富的容器和算法供开发者选用，但在某些特定场景下仍需权衡效率与易用性的取舍。对于非常庞大的数据集来说，传统的 I/O 函数如 `scanf` 和 `printf` 往往表现得更加迅速；然而当项目规模较小或者开发时间有限的情况下，则完全可以依赖于更简洁直观的标准流操作符 `<`, `>` 进行交互[^4]。

### 单调队列的C语言实现 单调队列是一种特殊的队列，其中元素按照某种特定的顺序排列（通常是递增或递减）。为了在C语言中实现单调队列，可以借助数组模拟队列的操作，并通过维护前后指针来控制队列的行为。 以下是基于循环队列的思想实现的一个单调递增队列的例子： ```c #include <stdio.h> #define MAX_SIZE 1000 // 队列的最大容量 typedef struct { int data[MAX_SIZE]; // 存储队列中的元素 int front; // 队头指针 int rear; // 队尾指针 } MonotonicQueue; // 初始化队列 void init(MonotonicQueue *mq) { mq->front = mq->rear = 0; } // 判断队列是否为空 int is_empty(MonotonicQueue *mq) { return mq->front == mq->rear; } // 判断队列是否已满 int is_full(MonotonicQueue *mq) { return (mq->rear + 1) % MAX_SIZE == mq->front; } // 入队操作，保持队列为单调递增 void push(MonotonicQueue *mq, int value) { while (!is_empty(mq) && mq->data[(mq->rear - 1 + MAX_SIZE) % MAX_SIZE] >= value) { mq->rear--; // 移除不符合条件的元素 } if (!is_full(mq)) { // 如果未满，则入队 mq->data[mq->rear++] = value; mq->rear %= MAX_SIZE; // 循环队列特性 } else { printf("Error: Queue is full.\n"); } } // 出队操作 void pop(MonotonicQueue *mq) { if (!is_empty(mq)) { mq->front++; mq->front %= MAX_SIZE; // 循环队列特性 } else { printf("Error: Queue is empty.\n"); } } // 获取队首元素 int get_front(MonotonicQueue *mq) { if (!is_empty(mq)) { return mq->data[mq->front]; } else { printf("Error: Queue is empty.\n"); return -1; // 返回错误码 } } int main() { MonotonicQueue mq; init(&mq); push(&mq, 3); push(&mq, 1); push(&mq, 2); printf("Front element: %d\n", get_front(&mq)); // 输出最小值 1 pop(&mq); printf("Front element after pop: %d\n", get_front(&mq)); // 输出次小值 2 return 0; } ``` 上述代码实现了一个简单的单调递增队列。它利用了循环队列的概念[^2]，并通过调整`push`函数逻辑确保队列内的元素始终满足单调性要求[^3]。 #### 关键点解析 - **初始化**：定义了一个结构体用于表示队列，包含存储数据的数组以及前後指针。 - **单调性维持**：在`push`方法中加入判断逻辑，当新元素小于等于当前队尾元素时，删除队尾元素直到恢复单调性为止[^4]。 - **边界处理**：考虑到了队列可能溢出的情况，在实际应用中可以根据需求动态扩展大小。 ### 注意事项 由于此实现采用了固定长度的数组作为底层容器，因此需要提前设定好最大容量(MAX_SIZE)，并注意防止越界访问等问题的发生。