在队列的基础上维护一个单调性的数据结构:单调队列

在栈的基础上维护一个单调性的数据结构:单调栈

单调队列

时间复杂度:$O(n)$

代码实现:

// value[ ]: 储存数据的数组
// n: 需要计算的范围
// q: STL双向队列,储存value[ ]中元素的数组序号
// k: 给定的区间大小
deque<int> q;
for (int i = 0; i < n; i++)
{
    // 去尾操作
    // 此为单调递增序列,若需要单调递减序列,将下一行的>改为<
    while (!q.empty() && value[q.back()] > value[i])
    {
        q.pop_back();
    }
    // 新元素(的序号)入队
    q.push_back(i);
    // 判断是否需要进行下面两个操作
    if (i >= k - 1)
    {
        // 删头操作
        while (q.front() < i - k + 1)
        {
            q.pop_front();
        }
        // 输出操作
        printf("%d ", value[q.front()]);
    }
}

典型题型:

POJ2823 - Sliding Window: http://poj.org/problem?id=2823

数据结构思路:(以单调递减序列为例)

流程:去尾操作 -> 入队操作 -> 删头操作 -> 输出操作 -> (循环)

去尾操作:

  1. 若队列为空:直接跳到下一步
  2. 若队列非空,若当前序号对应的数字比队尾小(即符合单调递减):不去尾,跳到下一步
  3. 若队列非空,若当前序号对应的数字比队尾小(不符合单调递减):弹出队尾,再次比较,循环操作直到队尾符合条件或队列空

入队操作:

将当前数字对应的序号入队

(判断是否需要进行下面两个操作:当读取过的数据还没有k个时,不需要删头操作,也不需要输出)

删头操作:

  1. 若队首(也就是队列最大值)还处于当前区间内:则队首对应的数字就是区间最大值,不删头,跳到下一步
  2. 若队首(也就是队列最大值)处于当前区间外:弹出队首,再次比较,循环操作直到队首符合条件,此时队首对应的原数字就是区间最大值

输出操作:

输出队首序号对应到原数组中的数字,即当前区间最大值

单调栈

时间复杂度:$O(n)$

代码实现:

// value[ ]: 储存数据的数组
// n: 需要计算的范围
// s: STL栈,储存value[ ]中元素的数组序号
stack<int> s;
for (int i = 0; i < n; i++)
{
    // 删除操作
    // 此为单调递增栈,若需要单调递减序列,将下一行的>改为<。根据题目,可能还用得到>=、<=
    while (!s.empty() && value[s.top()] > value[i])
    {
        s.pop();
    }
    // 新元素(的序号)入队
    s.push(i);
}

典型题型:

POJ3250 - Bad Hair Day: http://poj.org/problem?id=3250

POJ2559 - Largest Rectangle in a Histogram: http://poj.org/problem?id=2559

数据结构思路:

与单调队列几乎一样,就是单调队列去掉了删头操作。

标签: 单调队列, 单调栈

添加新评论