滑动窗口最大值

*****************************************************************

如果使用纯暴力复杂度为(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;
}