1、生成窗口最大值数组有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：[4 3 5] 4 3 3 6 7 窗口中最大值为54 [3 5 4] 3 3 6 7 窗口中最大值为54 3 [5 4 3] 3 6 7 窗口中最大值为54 3 5 [4 3 3] 6 7 窗口中最大值为44 3 5 4 [3 3 6] 7 窗口中最大值为64 3 5 4 3 [3 6 7] 窗口中最大值为7如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。请实现一个函数，给定一个数组arr，窗口大小w。返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回[5,5,5,4,6,7]。2、最大值减去最小值小于或等于num的子数组数量给定数组arr和整数num，返回有多少个子数组满足如下情况:max(arr[i..j]) - min(arr[i..j]) <= nummax(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。如果数组长度为 N，请实现时间复杂度为 O(N)的解法。参考代码如下：C++ Code ## 需要C++ 11支持 ##
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include #defineLENGTH(Arr) (sizeof(Arr) /sizeof(Arr[0])) / @brief 生成窗口最大值数组 实现一个函数，给定一个数组arr，窗口大小w。返回一个长度为n-w+1的数组res res[i]表示每一种窗口状态下的最大值 @param arr[] int @param length int -数组长度 @param winLen int -窗口大小 @return vector / vector<int> SlidingWindowMaxArray(intarr[],intlength,intwinLen) { deque<int> maxQueue;// 双端队列，存储下标，对应元素降序排列 vector<int> ret;// 结果 for(inti =0; i < length; ++i) { /< 若当前元素>=队列尾部元素，则队列尾出队列 / while(!maxQueue.empty() && arr[maxQueue.back()] <= arr[i]) { maxQueue.pop_back(); } maxQueue.push_back(i);// 当前元素下标进入队列尾部 if(maxQueue.front() == i - winLen)// 当前窗口范围>w,则队列头部出队列 { maxQueue.pop_front(); } if(i >= winLen -1)// 初始时可能窗口范围<w { ret.push_back(arr[maxQueue.front()]); } } returnret; } / @brief 最大值减去最小值小于或等于num的子数组数量 给定数组arr和整数num，返回有多少个子数组满足如下情况: max(arr[i..j]) - min(arr[i..j]) <= num @param arr[] int @param length int @param num int @return int */ intAllLessNumSubArray(intarr[],intlength,intnum) { deque<int> minDeque; deque<int> maxDeque; intret =0; intlow =0; inthigh =0; while(low < length) { while(high < length) { while(!minDeque.empty() && arr[minDeque.back()] >= arr[high]) { minDeque.pop_back(); } minDeque.push_back(high); while(!maxDeque.empty() && arr[maxDeque.back()] <= arr[high]) { maxDeque.pop_back(); } maxDeque.push_back(high); if(arr[maxDeque.front()] - arr[minDeque.front()] > num)break; ++high; } if(minDeque.front() == low) minDeque.pop_front(); if(maxDeque.front() == low) maxDeque.pop_front(); ret += high - low; ++low; } returnret; } intmain() { intarr[] = {4,3,5,4,3,3,6,7}; for(autoval : SlidingWindowMaxArray(arr, LENGTH(arr),3)) { cout << val <<" "; } cout << endl;// 输出结果【5 5 5 4 6 7】 intarr1[] = {7,9,6,1,0, 7,5,4,4,4, 2,0,7,1,7, 2,5,3,1,9, 0,8,8,9,4, 2,3,6,9,8 }; cout << AllLessNumSubArray(arr1, LENGTH(arr1),5) << endl;// 79 return0; } |
原文链接: https://www.cnblogs.com/fengkang1008/p/4865106.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/222832
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
