JZTXT

笔记

发布时间 2023-07-09 10:27:34作者: Lsr_Konnyaku

Day 1

The First Class

蒟蒻太蒟了，所以前面没记笔记。

前面笔记推荐czh的：https://www.cnblogs.com/CheZiHe929/p/17538291.html

四.栈（stack）

核心函数同queue，除front变top。

```cpp

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    for(int i=1;i<=n-k+1;i++){
    int minv=a[i],maxv=a[i];
        for(int j=0;j<=k;i++){//枚举区间左端点
            minv=min(minv,a[i+j]);
            maxv=max(maxv,a[i+j]);
        }
        cout<<maxv-minv<<'\n';
    }
 return 0;   
}

五。单调队列

对，单调队列的特性就是这四个zhx写的字。（zhx：是笔的问题，我的字很好看的）

struct queueue{
	int a[1919810]={0};
	int head=1;
	int tail=0;
	void push(int x){
		a[++tail]=x;
	}
	void pop(){
		head++;
	}
	int top(){
		return a[head];
	}
	int back(){
		return a[tail];
	}
	int size(){
		return tail-head+1;
	}
};
queueue q;
int main(){
cin>>n>>k;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    for(int i=1;i<=k;i++){
q.push(a[i]);
    }
    cout<<q.top()<<endl;
    for(int i=2;i<=n-k+1;i++){
    q.push(a[i+k-1]);
        q.pop();
    }
    return 0;
}