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

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

单调队列

复杂度

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

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

($n$ 为计算范围)

代码实现

STL 队列

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

数组模拟队列

// val[ ]: 储存数据的数组
// n: 需要计算的范围
// k: 给定的区间大小
// q: 数组队列,储存val[ ]中元素的数组序号
// h, t: 队头、队尾指针,(0, -1)为空
int q[MAXN], h = 0, t = -1;
for (int i = 0; i < n; i++)
{
    while (h <= t && val[q[t]] > val[i])
        t--;
    q[++t] = i;
    if (i >= k - 1)
    {
        if (q[h] < i - k + 1)
            h++;
        cout << val[q[h]] << ' ';
    }
}

分析

(以单调递减序列为例)

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

去尾操作:

a. 若队列为空:直接跳到下一步

b. 若队列非空,若当前序号对应的数字比队尾小(即符合单调递减):不去尾,跳到下一步

c. 若队列非空,若当前序号对应的数字比队尾小(不符合单调递减):弹出队尾,再次比较,循环操作直到队尾符合条件或队列空

入队操作:

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

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

删头操作:

a. 若队首(也就是队列最大值)还处于当前区间内:则队首对应的数字就是区间最大值,不删头,跳到下一步

b. 若队首(也就是队列最大值)处于当前区间外:弹出队首,再次比较,循环操作直到队首符合条件,此时队首对应的原数字就是区间最大值

输出操作:

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

例题

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

单调栈

复杂度

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

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

($n$ 为计算范围)

代码实现

STL 栈

// val[ ]: 储存数据的数组
// n: 需要计算的范围
// s: STL栈,储存val[ ]中元素的数组序号
stack<int> s;
for (int i = 0; i < n; i++)
{
    // 删除操作
    while (!s.empty() && val[s.top()] > val[i])
        s.pop();
    // 输出操作
    cout << (s.empty() ? -1 : val[s.top()]) << ' ';
    // 新元素(的序号)入队
    s.push(i);
}

数组模拟栈

// val[ ]: 储存数据的数组
// n: 需要计算的范围
// s: 数组栈,储存val[ ]中元素的数组序号
// t: 栈顶指针,0为空
int s[MAXN], t;
for (int i = 0; i < n; i++)
{
    while (idx && num[s[t]] >= num[i])
        t--;
    cout << (!t ? -1 : val[s[t]]) << ' ';
    s[++t] = i;
}

分析

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

例题

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

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

标签: 单调队列, 单调栈

添加新评论