changed 4 years ago  
Published Linked with GitHub

單調隊列

依最大權重做單調隊列

入隊:

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

出隊:

  1. 直接拿出head的元素

實作:sliding Window
利用記錄陣列的索引值才能判斷該元素有沒有過期













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]]);
    }
}
Select a repo