介紹

單調列隊-Monotone-Queue/Stack

單調性，意思就是該序列內的元素是單調的，例如: {a1, a2, a3, a4, …, an}，其中滿足a1 <= a2 <= a3 <= … <= an，此時該序列即是單調遞增序列，單調遞減序列也是存在的喔!!

維持單調性，顧名思義就是要維持序列的單調性，單調遞增序列維持方法:

如果序列的長度固定，則判斷序列首的元素是否滿足條件，不滿足條件則放大序列首
每次加入元素時與序列尾比較，如果當前元素小於序列尾，將序列尾元素依序出列直到滿足條件

範例問題

Zerojudge-a813: 城市觀測

有N棟房子。對於任意AB兩棟房子，只要AB中間沒有房子的高度超過A或B，則A可看見B。求1~N每棟房子可看見的房子總數。

測資一，0<N<=300，0<H[i]<=1e5，3/17分測資二，0<N<=5000，0<H[i]<=1e5，3/17分測資三，0<N<=1e6，0<H[i]<=1e9，11/17分

範例測資 N=2，H={1,1}，ans=1+1=2 N=3，H={1,2,3}，ans=1+2+1=4 N=5，H={5,2,3,4,4}，ans=4+2+3+3+2=14

我們其實可以把解法簡化成，A看的到B，B就看的到A，所以可以把大樓排成一個由高到低的三角形，每次push值進去stack前都檢查一下有沒有大於stack.top()，有的話就把所有小於該值的元素pop掉，然後Ck+1，因為後面的大樓也都看不到這些被pop掉的元素(Line: 19)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(false);cin.tie(0);

using namespace std;

int kase, i, b[1000001];

int main() {_

    while (cin >> kase) {
        for (i = 0; i < kase; i++)
            cin >> b[i];

        stack<int> stk, stk2;
        long long ans = 0;
        for(i = 0; i < kase; i++) {
            long long int ck = 0;
            while (!stk.empty() && stk.top() < b[i])    // 維持嚴格遞減
                ck += stk2.top(), stk.pop(), stk2.pop(); // 因為出現比之前更高的大樓，所以i之後的大樓看不到小於i的大樓
                                                        // 就先把可以看到的總數加起來再pop掉
            if (!stk.empty() && stk.top() == b[i])      // 出現同高的大樓，所以只能看到大於b[i]高度的大樓
                ck += stk2.top(), stk2.top()++;

            else
                stk.push(b[i]), stk2.push(1);

            if (stk.size() > 1)                         // 一定可以看到左邊的大樓，前題是左邊有東西
                ck++;
            // cout << ck << " ";
            ans += ck;

        }
        cout << ans * 2 << endl;

    }

    return 0;
}

Algorithm:: Monotone-Queue/Stack

單調列隊 Monotone-Queue/Stack 的學習筆記。

介紹

範例問題