---
# System prepended metadata

title: 單調隊列

---

# 單調隊列

依最大權重做單調隊列

入隊:
1. 從最後面檢查是否有比我小的元素
2. 有的話就pop=>tail=tail-1
3. 重複步驟1.直到tail比我大
4. 把該元素放進去


出隊:

1. 直接拿出head的元素

實作:sliding Window
利用記錄陣列的索引值才能判斷該元素有沒有過期
```c=
for(int i=1;i<=n;i++){
    scanf("%d",&arr[i]);
    if(q[head]<=i-k) head++;  //判斷有沒有過期
    while(arr[q[tail]]<=arr[i]&&tail>=head){
        //  找到比arr[i]大的數
        tail--;
    }
    q[++tail]=i;  //放入queue
    if(i>=k){
        printf("%d ",arr[q[head]]);
    }
}
```