单调栈_单调队列和优先队列.md

单调栈,单调队列和优先队列

单调栈

可以高效率获取某个位置左右两侧比他大（或小）的元素, 而且总的时间复杂度为O(n)。

//单调递增栈
for(int i = 0; i < nums.size(); i++){
  while(!stk.empty() && stk.top() > nums[i]){
    ​stk.pop();
  }
  stk.push(nums[i]);
}

//单调递减栈
for(int i = nums.size() - 1; i >= 0; i--){
  while(! stk.empty() && nums[i] >= stk.top()){
    stk.pop();
  }         
  stk.push(nums[i]);
}

• 单调栈问题

单调队列

队列中元素之间的关系具有单调性, 而且队首和队尾都可以进行出队操作,只有队尾可以进行入队操作;(时间复杂度还是O(n);空间复杂度O(k),即窗口大小)

• 应用于滑动窗口, 用来优化DP;

// 单调队列 STL deque
// O(n) 
int n,k;
int a[1000010];
deque<int>que;

int main()
{
    for(int i=1;i<=n;i++)cin>>a[i];
    // min 
    // 这里队列保存的是元素的index 
    for(int i=1;i<=n;i++)
    {
        while(!que.empty() && a[que.back()]>a[i])
        {
            que.pop_back();// 去尾 
        }
        que.push_back(i);// 入队
        if(i>=k)
        {
            while(!que.empty() && que.front()<i-k+1)
            {
                que.pop_front();// 删头 
            }
        } 
    }
    while(!que.empty())que.pop_front();// 清空队列 

    // max
    for(int i=1;i<=n;i++)
    {
        while(!que.empty() && a[que.back()]<a[i])
        {
            que.pop_back();// 去尾 
        }
        que.push_back(i);
        if(i>=k)
        {
            while(!que.empty() && que.front()<i-k+1)
            {
                que.pop_front();// 去头 
            }
        }
    }
    return 0;
}

• 单调队列实现滑动窗口

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆(默认是大顶堆)
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

• c++优先队列(priority_queue)用法详解

总结:

• 单调栈、单调队列及优先队列