---
lang: zh-Hant-TW
dir: ltr
description: Monotonic queue（臺灣正體：單調佇列；大陆简体：单调队列）
---

# 單調佇列

## 單調棧（monotonic stack）

1. 建立一個stack，存pair：**{值, 位置}**
2. 從左到右，每次pop stack直到最高元素比自己大（目前位置減掉頂端，就是從當下往後數第一個比自己大的位置）
3. 原因：
* 如果目前值比stack的頂還大，那目前的值也一定比小於stack頂端的值還大（也就是前面步驟所pop掉的）。但卻不知道會不會大於stack頂端的值還大，所以要pop直到比自己還大。
* $O(2n) = O(n)$ 一個點最多走兩次
* 最佳化：二分搜（$O(n+logn)$）

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vci nums(n);
    rep(0, n) cin >> nums[i];
    stack<pair<int,int>> st;
    LL res = 0;
    rep(0, n) {
        while (!st.empty() && st.top().first<=nums[i]) {
            st.pop();
        }
        res += st.empty() ? i + 1 : i - st.top().S;
        st.push({nums[i], i});
    }
    cout << res << NL;
}

<https://judge.tcirc.tw/ShowProblem?problemid=d028>

## 單調佇列（monotonic queue）

* 跟單調棧一樣，但是多了要維持邊界
* 用deque，右邊做單調性維護，左邊做邊界維護
* $O(n)$