滑动窗口最大值 - C++ 题解 (暴力解法优化)
虽然题目要求使用暴力解法,但我们仍然可以进行一些优化,以降低时间复杂度。
思路:
1. 遍历每个窗口: 对于每个窗口起始位置,遍历窗口内的所有元素,找到最大值。
2. 优化搜索范围: 利用已知信息减少不必要的比较次数。
C++ 代码实现:
代码解释:
* 使用两层循环遍历每个窗口。
* 外层循环遍历窗口起始位置。
* 内层循环遍历窗口内元素,找到最大值。
* 优化:
* 将窗口第一个元素设为初始最大值,减少一次比较。
* 如果找到更大的元素,且该元素位置距离窗口结束不足 k,则说明该元素一定会出现在后续窗口中,无需继续遍历当前窗口。
复杂度分析:
* 最坏情况下,每个窗口都需要遍历 k 个元素,时间复杂度为 O(nk)。
* 最好情况下,第一个元素就是最大值,且后续元素都小于它,时间复杂度为 O(n)。
* 平均情况下,时间复杂度介于 O(n) 和 O(nk) 之间。
总结:
虽然是暴力解法,但通过优化搜索范围,可以降低平均时间复杂度。