6 条题解

  • 3
    @ 2021-8-7 21:01:04

    C++ :

    
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn=1e6+5;
    int a[maxn],q[maxn];
     
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,k,hh=0,tt=-1;//队头指针hh,队尾指针tt
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(i-k+1>0) cout<<" ";//因为格式化输出空格,i-k+1为当前窗口第一个元素下标
            if(hh<=tt&&q[hh]<i-k+1) hh++;//如果队头元素保存的下标比当前窗口第一个元素下标小,说明当前队头元素不在当前窗口内,就要删去(队头元素的下标不一定是每次窗口最左边的那个(有可能那个已经被删掉了),所以队列中要保存下标,根据下标来做这个判断)
            while(hh<=tt&&a[q[tt]]>a[i]) tt--;//只要当前队尾元素对应的数值比当前数大,则删去队列中当前的对尾元素,保证队列的单调递增,这里的循环不会造成超时,因为考虑最坏情况,每隔k个数才会遇见一个当前数比队列中所有元素都小,这样整个题的时间复杂度就为o(n/k*k)=o(n);
            q[++tt]=i;//然后每次把当前数的下标插入到队列尾
            if(i-k+1>=0) cout<<a[q[hh]];//这样每次o(1)地输出队头元素对应的数值即为当前窗口最小值
        }
        cout<<endl;
        //接下来,求最大值同上,让单调队列保证递减即可
        memset(q,0,sizeof q);
        hh=0,tt=-1;
        for(int i=0;i<n;i++){
            if(i-k+1>0) cout<<" ";
            if(hh<=tt&&q[hh]<i-k+1) hh++;
            while(hh<=tt&&a[q[tt]]<a[i]) tt--;
            q[++tt]=i;
            if(i-k+1>=0) cout<<a[q[hh]];
        }
        return 0;
    }
    
    • 1
      @ 2025-7-9 9:25:53
      #include<iostream>
      #include<cmath>
      #include<queue>
      using namespace std;
      
      const int N = 1e+2;
      
      int arr[N];
      int que[N];
      int head = 0;
      int tail = -1;
      deque<int>dq;  
      
      int main()
      {
      	int n ,k  ;
      	cin >> n >> k;
      	for(int i = 0; i < n; i++)
      		cin >> arr[i];
      	for(int i = 0; i < n; i++)
      	{	
      		while(tail >= head &&  arr[i] <= arr[que[tail]]) 
      			tail --; 
      		que[++ tail] = i;
      		if(i - que[head] >= k) head ++;
      		if(i >= k - 1)
      			cout << arr[que[head]] <<" ";
      	}
      	cout << endl;
      	for(int i = 0; i < n; i ++)
      	{
      		while(!dq.empty() &&  arr[i] >= arr[dq.back()]) 
      		{ 
      			dq.pop_back();
      		}
      		dq.push_back(i);
      		if(i - dq.front() >= k) dq.pop_front();
      		if(i >= k - 1)
      			cout << arr[dq.front()] <<" ";
      	}
      	return 0;
      	
      }
      
      
      • 1
        @ 2023-8-5 0:29:19

        这道题大意就是让我们求区间内的最大最小值,就是一道RMQ问题,可以用单调队列解决。

        单调队列,顾名思义就是一个所有元素都有单调性的队列,我们可以建立一个队列来维护这些数据。

        首先每加入新元素前,我们要检查队首是否还在需统计的区间中,若否,出队。

        其次,维护队列单调性。以区间最大值为例,如果当前元素比队尾元素大,就不停出队,直到元素不大于队尾元素为止。

        处理完后,区间的最大值就是队首元素,直接输出即可。

        以下为部分代码,为防止复制就没全贴上来了(笑):

        //区间最小值
        for(int i=1;i<=n;i++){
        		while(!q.empty()&&i-k>=q.front()){
        			q.pop_front();
        		}//检查队首是否还在需统计的区间中
        		while(!q.empty()&&a[i]<=a[q.back()]){
        			q.pop_back();
        		}//维护队列单调性
        		q.push_back(i);
        		if(i>=k){
        			cout<<a[q.front()]<<" ";
        		}//输出
        	}
        	cout<<endl;
        	q.clear();//一定要清空,因为你接下来还有算区间最大值
        
        • 1
          @ 2022-4-8 21:21:03
          #include<iostream>
          #include<cstring>
          #include<algorithm>
          #include<cstdio>
          #include<cstdlib>
          #include<cmath>
          using namespace std;
          int n,m;
          int q1[1000001],q2[1000001];
          int a[1000001];
          int min_deque()
          {
              int h=1,t=0;
              for(int i=1;i<=n;i++)
              {
                  while(h<=t&&q1[h]+m<=i) h++;
                  while(h<=t&&a[i]<a[q1[t]]) t--;
                  q1[++t]=i;
                  if(i>=m) printf("%d ",a[q1[h]]);
              }
              cout<<endl;
          }
          int max_deque()
          {
              int h=1,t=0;
              for(int i=1;i<=n;i++)
              {
                  while(h<=t&&q2[h]+m<=i) h++;
                  while(h<=t&&a[i]>a[q2[t]]) t--;
                  q2[++t]=i;
                  if(i>=m) printf("%d ",a[q2[h]]);
              }
          }
          int main()
          {
              cin>>n>>m;
              for(int i=1;i<=n;i++) scanf("%d",&a[i]);
              min_deque();
              max_deque();
              return 0;
          }
          
          • -2
            @ 2022-1-19 11:06:10

            #include #include<stdio.h> #include #include #include

            using namespace std;

            const int N=1e7+100; int q[N],a[N];

            int main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int l,r; l=r=1; for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]>=a[i]) { r--; } q[r++]=i; if(i-q[l]>=k) l++; if(i>=k) cout<<a[q[l]]<<" "; } cout<<endl; l=r=1; for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]<=a[i]) { r--; } q[r++]=i; if(i-q[l]>=k) l++; if(i>=k) cout<<a[q[l]]<<" "; } return 0; }

            • -2
              @ 2022-1-19 11:06:05

              给爷点赞!!!!(已防复制)


              #include<iostream> 
              #include<cstring>
              using namespace sd; 
              int n, a, l, r;
              int arr[1000005], q[1000005];
              int main(){
              	cin >> n >> a;
                  for(int i = 1; i <= n; i++) cin >> arr[i];
                  for(int i = 1; i <= n; i++){
                      int temp = arr[i];
                      while(r > l && arr[q[r-1]] >= temp)
                          r--;
                      q[r++] = i;
                      if(i - q[l] >= a)   l++;
                      if(i >= a)
                          cout << arr[q[l]] << ' ';
                  }
                  cout << endl;
                  l = r = 0;
                  for(int i = 1; i <= n; i++){
                      int temp = arr[i];
                      while(r > l && arr[q[r-1]] <= temp)
                          r--;
                      q[r++] = i;
                      if(i - q[l] >= a)   l++;
                      if(i >= a)
                          cout << arr[q[l]] << ' ':
                  }
                  return 0;
              }
              
              • 1

              信息

              ID
              65
              时间
              1000ms
              内存
              128MiB
              难度
              4
              标签
              递交数
              291
              已通过
              131
              上传者