荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
void PrintMax(A, 0, -1)调用函数。请斑竹指教,怎么感觉好像有点理解错题意了?
void PrintMax(long *A, int max, int k){
if (k > A.size()){
cout max)
max = A[k + i];
k += i;
}
PrintMax(A.substr(1), max, k); // 这里substr应该不可以用在long类型吧,不过写个移动的小函数也不难,怕麻烦。。不写了呵呵
}
2339923 发表于 2011-8-14 15:47 ![]()
你的意思就是维护一个大小为w的数组,每次更新这个数组并找最大值.
这样时间复杂度就是O(wn).
应为每次找最大值,可以考虑用最大堆来替代这个数组,这样时间复杂度就是O(logw * n)
仔细考虑可以发现没有必要每次维护w个数,比如当window是1,2,5,4,3,2时, window
右移一位或两位的时候, 答案都是5, 所以,没必要维护全部数据,维护 5432就ok了.考虑
用一个队列来维护窗口,时间复杂度可以做到O(n), 代码如下:
- void AddOne(deque<int>& que, int a[], int i)
- {
- assert(a && i >= 0);
- while (!que.empty() && a[que.back()] < a[i])
- que.pop_back();
- que.push_back(i);
- }
- void PrintWindow(int a[], int n, int w)
- {
- assert(a && n > 0 && w > 0 && n >= w);
- deque<int> que;
- for (int i = 0; i < w; i++)
- AddOne(que, a, i);
- cout<<a[que.front()]<<endl;
- for (int i = 1; i+w-1 < n; i++)
- {
- if (i-1 == que.front())
- que.pop_front();
- AddOne(que, a, i+w-1);
- cout<<a[que.front()]<<endl;
- }
- }
复制代码 |
|