7月24号题解
滑动窗口最大值
*****************************************************************
如果使用纯暴力复杂度为(k*n) 但使用单调队列的方式可以让复杂度变为(n) ,单调队列的方式,维护一个单调递减的队列,我们让队首永远维护这个滑动窗口的最大值,将边界设为(1-k,n-k),当i比0大的时候就可以队列的首项就是这个窗口的最大值
{
// 使用双端队列来维护滑动窗口中的最大值索引
deque<int> p;
vector<int> ans(nums.size() - k + 1);
// 初始化循环变量,i 用于结果数组的索引,j 用于遍历 nums 数组
// 注意这里 i 的初始值是 1-k,因为当 j=0 时,窗口还未完全形成(除非 k=1)
// 所以此时不记录结果到 ans 中
for(int j = 0, i = 1 - k; j < nums.size(); i++, j++)
{
// 如果当前窗口的起始位置已经超过了数组边界,并且队列的前端是该起始位置的元素
// 那么移除它,因为新的窗口已经不包含它了
if(i > 0 && p.front() == nums[i - 1])
{
p.pop_front();
}
// 移除队列后端所有小于当前元素的索引,因为它们不可能是当前窗口的最大值
while(!p.empty() && p.back() < nums[j])
{
p.pop_back();
}
// 将当前元素的索引加入队列
p.push_back(j);
// 如果当前窗口的起始位置已经在数组范围内,记录当前窗口的最大值到结果数组中
// 队列的前端始终是窗口中的最大值索引
if(i >= 0)
{
ans[i] = nums[p.front()];
}
}
// 返回包含每个窗口最大值的数组
return ans;
}js
单调栈找左右比它小的值
单调栈可以找到某个数后面比它(大或小的数),但现在要解决的是如何维护左右的比它小的值呢。当某个数比它小是我们就可以把栈顶弹出,这里想一下是什么样的数被它压着,前面说了小的能使大的弹出,说明被它压住的是比它小的。当判断完我们会发现栈里还有剩的,说明后面已经没有让它们可以弹出栈的条件了。但左区间还没有判断完。所以要把栈清空
using namespace std;
const int N=1e5+10;
int a[N],l[N],r[N];
/*
例子 8
2 5 6 7 3 4 1 8
左 -1 1 2 3 1 5 -1 7
右 7 5 5 5 7 7 -1 -1
*/
int main()
{
stack<int> p;
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
l[i]=r[i]=-1;//初始化
}
for(int i=1;i<=n;i++)
{
while(!p.empty()&&a[p.top()]>a[i])
{//栈非空且入栈元素小于栈顶,需要清算
int cur=p.top();//弹出当前栈顶
p.pop();
r[cur]=i;//右边第一个小的元素是 i
if(!p.empty()) l[cur]=p.top();// 左边第一个小的数是当前栈顶
}
p.push(i);//栈内单调性调整完毕,压入 i
}
while(!p.empty())// 栈内留下的未弹出的元素
{
int cur=p.top();
p.pop();
if(!p.empty()) l[cur]=p.top();
//最后清算阶段的元素只有左边小,没有右边
}
for(int i=1;i<=n;i++)
{
cout<<l[i]<<' ';
}
cout<<endl;
for(int i=1;i<=n;i++)
{
cout<<r[i]<<' ';
}
return 0;
}
#题解#