网站建设产品展示,返利网app网站开发,做企业网站怎么样,网站生成系统源码1 问题
给定一个数组和滑动窗口的大小#xff0c;请找出所有滑动窗口里的最大值#xff0c;列如#xff0c;数组#xff5b;2,3,4,2,6,2,5,1#xff5d;的滑动窗口大小是3#xff0c;一起6个滑动窗口#xff0c;分别是{4#xff0c;4#xff0c;6#xff0c;6#…1 问题
给定一个数组和滑动窗口的大小请找出所有滑动窗口里的最大值列如数组2,3,4,2,6,2,5,1的滑动窗口大小是3一起6个滑动窗口分别是{44665} 2 分析
2,3,4,2,6,2,5,1 我们这里可以用双端队列滑动窗口是3我们先找出前3个数字里面的最大值放在双端队列的头然后依次向右滑动确保每次滑动后队列的头是最大值。 3 代码实现
#include iostream
#include vector
#include dequeusing namespace std;vectorint maxWindows(const vectorint nums, int size)
{vectorint maxWindows;if (size 0 || nums.size() 0 || (nums.size() size)){return maxWindows;}dequeint indexs;for (int i 0; i size; i){while (indexs.size() 0 nums[i] nums[indexs.back()]){indexs.pop_back();}indexs.push_back(i);}for (int i size; i nums.size(); i){maxWindows.push_back(nums[indexs.front()]);while (indexs.size() 0 nums[i] nums[indexs.back()]){indexs.pop_back();}while (indexs.size() 0 (i - indexs.front() size)){indexs.pop_front(); }indexs.push_back(i);}maxWindows.push_back(nums[indexs.front()]);return maxWindows;
}int main()
{vectorint nums;nums.push_back(2);nums.push_back(3);nums.push_back(4);nums.push_back(2);nums.push_back(6);nums.push_back(5);nums.push_back(2);nums.push_back(1);vectorint result;result maxWindows(nums, 3);if (result.size() 0){for (int i 0; i result.size(); i)std::cout result[i] std::endl;}return 0;
} 4 运行结果
4
4
6
6
6
5 5 总结
在一个数组里面通过双端队列qedue求最大值 std::dequeint indexs;std::vectorint nums;nums.push_back(1);nums.push_back(3);nums.push_back(2);nums.push_back(5);nums.push_back(4);for (int i 0; i nums.size(); i){while (indexs.size() 0 nums[i] nums[indexs.back()]){indexs.pop_back();}indexs.push_back(i);}std::cout maxValue is nums[indexs.front()] std::endl;
