acwing刷题指南7

//数据结构篇

好像单链表和双链表没写到上面来，不过没事，后面图论再写

题目列表：

828. 模拟栈

829. 模拟队列

830. 单调栈（找在右边比自己小的数，构成单调递增区间（反之））

154. 滑动窗口（类似于单调栈不过又像极了双端队列）

都可以画图解释

828. 模拟栈

模板题

有手就行

#include
using namespace std;
const int N = 100010;
int stk[N],tt;
int m;
void push(int x)
{
    tt++;
    stk[tt] = x;
}
void pop()
{
    tt--;
}
void empty()
{
    if(tt)cout<<"NO"<     else cout<<"YES"< }
int query()
{
    return stk[tt];
}

int main()
{
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        if(op == "push")
        {
            int x;
            cin>>x;
            push(x);
        }
        else if(op == "pop")pop();
        else if(op == "empty")empty();
        else cout<     }
    return 0;
}

829. 模拟队列（有手就行）

#include
#include
using namespace std;
const int N = 100010;
int hh,tt=-1,q[N],n;
int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        string op;
        cin>>op;
        if(op == "push")
        {
            cin>>x;
            q[++tt] = x;
        }
        else if(op == "pop") hh++;
           
        else if(op == "empty")cout<<(hh <= tt ? "NO":"YES")<         
        else cout<     }
    return 0;
}

830. 单调栈

#include
using namespace std;
const int N = 100010;
int stk[N],tt;
int n;
int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        while(tt && stk[tt] >= x)tt--;
        if(!tt)cout<<"-1"<<" ";
        else cout<         stk[++tt] = x;
    }
    return 0;
}

154. 滑动窗口(求最大最小可以镜像求解即可)

#include
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];//a[N]表示原数组，q[N]表示单调队列
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

//86ms的速度快吧

    cin>>n>>k;
    for(int i = 0;i < n;i++)cin>>a[i];
    
    int hh = 0,tt = -1;
    for(int i = 0;i < n;i++)
    {
        if(hh <= tt && i-k+1 > q[hh])hh++;
        while(hh <= tt && a[q[tt]] >= a[i])tt--;
        q[++tt] = i;
        
        if(i >= k-1) cout<     }
    cout<     
     hh = 0,tt = -1;
    for(int i = 0;i < n;i++)
    {
        if(hh <= tt && i-k+1 > q[hh])hh++;
        while(hh <= tt && a[q[tt]] <= a[i])tt--;
        q[++tt] = i;
        if(i >= k-1)cout<         
    }
   cout<     return 0;
}