spoj ARRAYSUB:O(n)复杂性方法

Question

我试图在spoj http://spoj.pl/problems/ARRAYSUB上解决这个问题

我用两种方法解决了它

首先使用优化的蛮力.其次采用Pivot在k,2k,3k等等并找到最大值.

虽然在最坏的情况下接受两种解决方案,但复杂性是O(n*k);

任何人都可以建议O(n)解决方案解决问题.

下面是我的运行接受的最坏情况复杂度O(n*k)的代码:

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
main()
{
    long n;
    cin >> n;
    long *arr = new  long[n];
    for( long i=0;i<n;i++)
        cin >> arr[i];
     long k;
    cin >> k;
     long max=arr[0];
    for(long i=1;i<k;i++)
    {
        if(arr[i]>max)
            max=arr[i];
    }
    if(k!=n)
    cout<<max<<" ";
    else cout<<max;
    for( long i=k;i<n;i++)
    {
        if(arr[i-k]==max)
        {max=-1;
        for(int j=i-k+1;j<=i;j++)
        if(arr[j]>max)
        max=arr[j];
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;

        }
        else{
        if(arr[i]>max)
        {   max=arr[i];

        if(i!=n)
        cout<<max<<" ";
        else 
        cout<<max;
        }
        else
        {
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;}
        }
    }

        cout<<endl;
    return(0);
}

Answer 1

在O(n)时间内用于解决此问题的数据结构是"deque"

大多数人认为的一种自然方式是尝试保持队列大小与窗口大小相同.试着摆脱这种想法,试着在盒子外思考.删除冗余元素并仅存储需要在队列中考虑的元素是实现下面的高效O(n)解决方案的关键.

  void maxInWindow(vector<int> &A, int n, int k, vector<int> &B) {
  deque<int> Q;
  for (int i = 0; i < k; i++) {
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    Q.push_back(i);
  }
  for (int i = k; i < n; i++) {
    B[i-k] = A[Q.front()];
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    while (!Q.empty() && Q.front() <= i-k)
      Q.pop_front();
    Q.push_back(i);
  }
  B[n-k] = A[Q.front()];
  //B stores the maximum of every contiguous sub-array of size k    
}

说明:

第一个for循环计算第一个'k'元素的最大值,并将索引存储在Q.front().这变成B [0] = A [指数].下一节,如果A [i]大于先前存储的最大值,我们将从后面推动并弹出.如果索引的值小于ik,我们会从前面弹出,这意味着它不再相关.