查找每个 k 大小的连续子数组的最大值的 C++ 程序
假设我们有一个包含n个元素和一个值k的数组。我们必须为每个大小为k的连续子数组找到最大值。
所以，如果输入像arr=[3,4,6,2,8],k=3，那么输出将是大小为3的连续子数组是[3,4,6],[4,6,2],[6,2,8]，所以最大元素是6、6和8。
示例
让我们看看以下实现以获得更好的理解-
#include#include #include using namespace std; int main(){ vector arr = {3,4,6,2,8}; int k = 3; deque Qi(k); int i; for (i = 0; i < k; ++i){ while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); Qi.push_back(i); } for ( ; i < arr.size(); ++i){ cout << arr[Qi.front()] << " "; while ( (!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front(); while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); Qi.push_back(i); } cout << arr[Qi.front()] << endl; }
输入
{3,4,6,2,8}, 3输出结果6 6 8