滑動窗口中的最大值

-4

我無法檢測到爲什麼我在spoj上給出的問題子數組中出現錯誤答案。問題是確定k大小的窗口中的最大元素。我已經應用了使用deque的滑動窗口算法，並且始終保持最大元素的索引位於前面。滑動窗口中的最大值

這裏是我的代碼：

#include<iostream> 
#include<deque> 
using namespace std; 

int main() 
{ 
    int n; 

    cin>>n; 

    int arr[n]; 
    for(int i=0;i<n;i++) 
    { 
     cin>>arr[i]; 
    } 
    int k; 
    cin>>k; 

    deque<int>q; 
    int ans[n-k+1]; 
    for(int i=0;i<k;i++) 
    { 
     while(!q.empty()&&arr[i]>=arr[q.back()]) 
      q.pop_back(); 

     q.push_back(i); 
    } 

    for(int i=k;i<n;i++) 
    { 
     ans[i-k]=arr[q.front()]; 

     while(!q.empty()&&arr[i]>=arr[q.back()]) 
      q.pop_back(); 

     while(!q.empty()&&q.front()<=i-k) 
      q.pop_front(); 

     q.push_back(i); 
    } 
    ans[n-k]=arr[q.front()]; 

    for(int i=0;i<=n-k;i++) 
    { 
    cout<<ans[i]; 
    } 
    cout<<"\n"; 

    return 0; 
}

來源

2015-08-15 Seetu Agarwal

縮進你的代碼，所以它的可讀性。你有沒有嘗試過使用調試器來查看它出錯的地方？你沒有說出你得到什麼樣的錯誤。 –

目前還不清楚你的代碼在做什麼。但我認爲你可以用數組解決這個問題，這也會更簡單。 – xashru

我得到正確的答案與在spoj網站上給出的測試案例，但仍然得到錯誤的答案，當我提交他們，我認爲一些測試案例失蹤找不到他們？我正在使用leetcode.com上給出的滑動窗口算法......我正在解決關於spoj的ARRAYSUB問題 –

簡單的C++邏輯會...

#include <iostream> 
#include<stdio.h> 
int main() { 
int temp; 
int A[] = {1,2,-1,7,8,-3,-4}; 
int max = A[0]; 
printf("%d\n",max); 
int n = 7; 
for(int i = 1 ; i <= n; i++) 
{ 
    for(int j = 0; j <= n-i ; j++) 
    { 
     temp = 0; 
     for(int k = 0; k < i; k++) 
     { 
      temp+=A[j+k]; 
     } 
     if(temp > max) 
     max = temp; 
     //printf("%d\n",max); 
    } 
} 
printf("%d\n",max); 
return 0; 
}

來源

2015-09-16 04:34:40

滑動窗口中的最大值

回答

相關問題