洛谷：P1440 求m区间内的最小值（普及/提高-，滑动窗口）

题目：

代码：3个点超时，懵逼：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int A[2000005];
int main()
{
 cout<<0<<endl;
 cin>>m>>n; 
 deque<int> dq;
 cin>>A[0];
 cout<<A[0]<<endl;
 dq.push_back(0);
 //形成最初窗口 
 for(int i=1;i<n;i++)
 {
  scanf("%d",&A[i]);
  //倒着找比该元素小的，都弹出 
  while(!dq.empty())
  {
   if(A[dq.back()]>=A[i]) dq.pop_back();
   else break;
  }
  dq.push_back(i);
  cout<<A[dq.front()]<<endl;
 }
 //cout<<A[dq[0]]<<endl;
 for(int i=n;i<m-1;i++)
 {
  scanf("%d",&A[i]);
  //倒着找比该元素小的，都弹出 
  while(!dq.empty())
  {
   if(A[dq.back()]>=A[i]) dq.pop_back();
   else break;
  }
  dq.push_back(i);
  //第一个是否已出
  if(dq.front()<i-n+1) dq.pop_front();
  cout<<A[dq[0]]<<endl;
 }
}

题解差不多：

题解：

1.不存下标，创了个结构体里面放了下标和值。

2.压缩了循环和判断条件，代码简洁了很多。

但我的超时感到懵逼。