FZU 1894：單調隊列維護滑動窗口最大值

問題描述

面試隊列操作：

• C NAME RP：NAME（RP值）入隊。
• G：隊首出隊。
• Q：查詢當前隊列最大 RP 值。

多測試用例，以 END 結束每組。

單調隊列技巧

• 維護一個**下標遞增、值遞減**的雙端隊列 q，存儲 {index, value}。
• 入隊時，從隊尾彈出所有 value ≤ 新值 的元素，再壓入新元素（保證隊列遞減，隊首為最大值）。
• 出隊時，若隊首下標等於出隊元素的全局序號，彈出隊首。
• 查詢時，隊首即為最大值（若隊列為空輸出 -1）。

代碼

struct Node { int idx, val; } q[1000000];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char op[10], name[10]; int rp;
        scanf("%s", op); // 讀第一個 END? 實際輸入格式需注意
        int head=0, tail=-1, lastOutIdx=0, globalIdx=1;
        while (scanf("%s", op) && strcmp(op, "END")) {
            if (op[0]=='C') {
                scanf("%s%d", name, &rp);
                while (tail>=head && q[tail].val <= rp) tail--;
                q[++tail] = {globalIdx++, rp};
            } else if (op[0]=='Q') {
                while (tail>=head && q[head].idx <= lastOutIdx) head++;
                if (tail>=head) printf("%d\n", q[head].val);
                else printf("-1\n");
            } else { // G
                lastOutIdx++;
            }
        }
    }
}

關鍵點

• 全局遞增索引 globalIdx 標記入隊順序，lastOutIdx 記錄已出隊數，配合判斷隊首是否過期。
• 單調隊列實現 O(1) 入隊、出隊、查詢最大值，總體線性。