题目
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
参数范围:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
单调栈
时间复杂度😮(n)。
queMax中记录(i-k,i],如果i1 < i2,且nums[i1] <=nums[i2],那么i1无论如何都无法成为最大值。故可以淘汰i1,淘汰i1后,成降序排列。队首元素最大。
对queMax有三种操作。
操作一 | 队尾淘汰i1 |
操作二 | 队尾插入i2 |
操作三 | 队首删除i-k,由于操作二,queMax不会为空,所以无需判断是否为空。如果i-k已经被操作一淘汰,则不能删除。 |
代码
核心代码
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int i = 0; std::deque<int> queMax; vector<int> vRet; for ( i = 0; i < k; i++) { while (queMax.size() && (nums[queMax.back()] <= nums[i])) { queMax.pop_back(); } queMax.emplace_back(i); } vRet.emplace_back(nums[queMax.front()]); for (; i < nums.size(); i++) { if (i - k == queMax.front()) { queMax.pop_front(); } while (queMax.size() && (nums[queMax.back()] <= nums[i])) { queMax.pop_back(); } queMax.emplace_back(i); vRet.emplace_back(nums[queMax.front()]); } return vRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; int k; { Solution sln; nums = { 1, 3, -1, -3, 5, 3, 6, 7 }, k = 3; auto res = sln.maxSlidingWindow(nums, k); Assert(vector<int>{ 3,3,5,5,6,7 }, res); } { Solution sln; nums = { 1 }, k = 1; auto res = sln.maxSlidingWindow(nums, k); Assert(vector<int>{ 1 }, res); } //CConsole::Out(res); }
2023年3月二叉树
用多键二叉树(红黑树)mulset记录滑动窗口中的数,由于二叉树默认是升序排列,所以最后一个元素,就是最大值。由于二叉树的插入、删除的时间复杂度是O(logn),故总时间复杂度是O(nlogn) 。
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int i = 0; std::multiset<int> setNums; for (; i + 1 < k; i++) { setNums.insert(nums[i]); } vector<int> vRet; for (; i < nums.size(); i++) { setNums.insert(nums[i]); vRet.push_back(*setNums.rbegin()); auto it = setNums.find(nums[i + 1 - k]); setNums.erase(it); } return vRet; } };
2023年3月第二版
class Solution { public: vector maxSlidingWindow(vector& nums, int k) { vector> vValueIndex; vector vRet; int iPos = 0; for (int i = 0; i < nums.size(); i++) { while ( ( vValueIndex.size() > iPos ) && (nums[i] >= vValueIndex.back().first)) { vValueIndex.pop_back(); } vValueIndex.emplace_back(nums[i], i); if (i + 1 >= k) { vRet.push_back(vValueIndex[iPos].first); } if (i + 1 - k == vValueIndex[iPos].second) { iPos++; } } return vRet; } };
2023年8月版
class Solution{ public: vector maxSlidingWindow(vector&nums, int k) { m_c = nums.size(); //每k个元素用一组,vLeft各元素到组首的最大值,vRight各元素到组尾的最大值 vector vLeft(m_c), vRight(m_c); int iMax = 0; for (int i = 0; i < m_c; i++) { if (0 == i % k) { iMax = nums[i]; } else { iMax = max(iMax, nums[i]); } vLeft[i] = iMax; } iMax = -100 * 1000; for (int i = m_c-1;i >= 0 ; i-- ) { if (0 == (i+1) % k) { iMax = nums[i]; } else { iMax = max(iMax, nums[i]); } vRight[i] = iMax; } vector vRet; for (int i = k-1; i < m_c; i++) { vRet.emplace_back( max(vRight[i-k+1], vLeft[i])); } return vRet; } int m_c; };
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用C++ 实现。