资格证网站怎么做,东莞大朗现在有多少例,html简单网页模板,淘宝关键词top排行榜作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调双向队列 二叉树
题目
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动…作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调双向队列 二叉树
题目
给你一个整数数组 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:vectorint maxSlidingWindow(vectorint nums, int k) {int i 0;std::dequeint queMax;vectorint 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;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorint nums;int k;{Solution sln;nums { 1, 3, -1, -3, 5, 3, 6, 7 }, k 3;auto res sln.maxSlidingWindow(nums, k);Assert(vectorint{ 3,3,5,5,6,7 }, res);}{Solution sln;nums { 1 }, k 1;auto res sln.maxSlidingWindow(nums, k);Assert(vectorint{ 1 }, res);}//CConsole::Out(res);
}2023年3月二叉树
用多键二叉树红黑树mulset记录滑动窗口中的数由于二叉树默认是升序排列所以最后一个元素就是最大值。由于二叉树的插入、删除的时间复杂度是O(logn)故总时间复杂度是O(nlogn) 。 class Solution {public:vectorint maxSlidingWindow(vectorint nums, int k) {int i 0;std::multisetint setNums;for (; i 1 k; i){setNums.insert(nums[i]);}vectorint 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) { vectorpairint, int 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(vectornums, 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 (i1) % 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-k1], 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C 实现。
