栈¶
单调栈¶
思想¶
- 从栈底到栈顶，元素具有单调性质，push一个元素前可能要先进行多次pop，维护单调性质
- 常用于找到下一个更大或更小元素（o(n)）
例题¶
-
难（想不到，不明显）
-
- 为了便于操作，使用deque来模拟栈
- 1124. 表现良好的最长时间段
- 前缀和
- 单调队列思想
矩形问题¶
例题¶
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
vector<vector<int>>check(mat.size(),vector<int>(mat[0].size(),0));
int ans=0;
for(int i=0;i<mat.size();i++)
{
if(mat[i][0]==1)
check[i][0]=1;
for(int j=1;j<mat[0].size();j++)
{
if(mat[i][j]==1)
check[i][j]=check[i][j-1]+1;
}
}//预处理，一个位置前面有多少个连续的1
for(int j=0;j<mat[0].size();j++)
{
stack<pair<int,int>>s;//存储长度及高度
s.emplace(0,0);//哨兵
int sum=0;//存储新增行之前的总数
for(int i=0;i<mat.size();i++)
{
int h=1;
while(check[i][j]<s.top().first)
{
sum-=(s.top().first-check[i][j])*s.top().second;//前面行不能再用的元素
h+=s.top().second;//新高度
s.pop();
}
s.emplace(check[i][j],h);
sum+=check[i][j];
ans+=sum;
}
}
return ans;
}
};
贡献法¶
思想¶
- 确定每一个元素对结果答案的贡献
- 比较简洁的一个写法
vector<int> left(n, -1); // left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1） vector<int> right(n, n); // right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n） stack<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && strength[st.top()] >= strength[i]) { right[st.top()] = i; st.pop(); } if (!st.empty()) left[i] = st.top(); st.push(i); }
例题¶
- （典）907. 子数组的最小值之和
class Solution { public: int sumSubarrayMins(vector<int>& arr) { int ans=0,mod=1000000007; vector<int>left(arr.size(),0),right(arr.size(),0);//一个元素到前/后一个更小值的距离（即其是子数组内最小元素的范围） stack<int>s; for(int i=0;i<arr.size();i++)//向后找 { while(!s.empty()&&arr[i]<arr[s.top()]) { right[s.top()]=i-s.top(); s.pop(); } s.push(i); } while(!s.empty()) { right[s.top()]=arr.size()-s.top(); s.pop(); } for(int i=arr.size()-1;i>=0;i--)//向前找 { while(!s.empty()&&arr[i]<=arr[s.top()]) { left[s.top()]=s.top()-i; s.pop(); } s.push(i); } while(!s.empty()) { left[s.top()]=s.top()+1; s.pop(); } for(int i=0;i<arr.size();i++) { ans=(ans+((long long)(left[i]*right[i])%mod*arr[i])%mod)%mod; } return ans; } }; - (难)2281. 巫师的总力量和
- 数学推导
栈的应用¶
解决括号问题¶
- 394. 字符串解码
- P5658 括号树
- 树上匹配
队列¶
优先队列¶
思想¶
- 单调栈/队列是：及时移除无用数据，保证队列/栈的有序性。
- 优先队列则是一个堆，可以理解为边插入边排序，并不是通过删除元素的方式维持元素的有序性。此外，单调栈/队列是指其中所有元素呈现单调递增或递减，而优先队列是一个堆，只维护最大/小值，元素并不一定是有序排列的。
支持删除的优先队列¶
-
使用set或者双队列模拟
-
懒删除，一个队列维护全部元素，另一个维护要删除的队列，由于使用相同的排列顺序，因此要删除的元素优先级相同
-
```c++ template
> class LazyPriorityQueue { private: std::priority_queue // 私有方法，用于清除标记为删除的元素 void cleanTop() { while (!mainQueue.empty() && !deleteQueue.empty() && mainQueue.top() == deleteQueue.top()) { mainQueue.pop(); deleteQueue.pop(); } }
public: void insert(const T& element) { mainQueue.push(element); }
void lazyDelete(const T& element) {
deleteQueue.push(element);
cleanTop(); // 清理主队列顶部的删除元素
}
T top() {
cleanTop(); // 清理主队列顶部的删除元素
if (mainQueue.empty()) {
throw std::runtime_error("Queue is empty.");
}
return mainQueue.top();
}
bool isEmpty() const {
return mainQueue.empty() && deleteQueue.empty();
}
}; ```
例题¶
- 剑指 Offer 41. 数据流中的中位数
- 同时维护一个大顶堆一个小顶堆，存储较小的一部分和较大的一部分。
- 6306. 过桥的时间
- 复杂堆模拟
- 358. K 距离间隔重排字符串
- 218. 天际线问题
- P2672 推销员 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
单调队列（deque）¶
思想¶
- 由于不仅可以从尾部操作，还可以从头部操作，因此比单调栈更为灵活
- 除了维护单调性质外（通常队首的元素优先级最高），优先级越高的元素也会越先失效出队(这就是比单调栈更灵活的地方)
模版¶
for(int i=1;i<arr.size();i++)
{
while(!dq.empty()&&arr[i]-arr[dq.front()]>=k)//队首出队
{
ans=min(ans,i-dq.front());
dq.pop_front();
}
while(!dq.empty()&&arr[i]<=arr[dq.back()])//队尾维护
dq.pop_back();
dq.push_back(i);
}
例题¶
- 面试题59 - II. 队列的最大值
- 239. 滑动窗口最大值
- 有时可以用multiset代替单调队列来解题，不过效率更低（nlogn）
- 862. 和至少为 K 的最短子数组
- 边从队尾添加并维持单调，边从队首出队
- 1687. 从仓库到码头运输箱子
- 动态规划结合单调队列（难）
- NOIP2017 普及组] 跳房子
- 单调队列优化动态规划
随机队列¶
- 随机队列与普通队列相比，除了 pop 随机元素而非队头元素之外，没有其它变化。
- pop 的实现：选出随机下标后，将对应元素与 vector 的尾部元素交换，然后将将尾部弹出。
例题¶
循环队列¶
-
使用数组静态实现
-
```c++ struct myqueue{ int data[N]; //分配静态空间 / 如果动态分配，这样写： int data; / int head, rear; //队头、队尾 bool init(){ //初始化 /如果动态分配，这样写： Q.data = (int )malloc(N * sizeof(int)) ; if(!Q.data) return false; / head = rear = 0; return true; } int size(){ return (rear - head + N) % N;} //返回队列长度
bool empty(){ //判断队列是否为空 if(size()==0) return true; else return false; } bool push(int e){ //队尾插入新元素。新的rear指向下一个空的位置 if((rear + 1) % N == head ) return false; //队列满 data[rear] = e; rear = (rear + 1) % N; return true; } bool pop(int &e){ //删除队头元素，并返回它 if(head == rear) return false; //队列空 e = data[head]; head = (head + 1) % N; return true; } int front(){ return data[head]; } //返回队首，但是不删除
}Q;```