备案 网站名称什么用,百度自然搜索排名优化,平顶山网站网站建设,为什么有的网站只有版权没有备案作者推荐
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值
本文涉及的基础知识点
C算法#xff1a;滑动窗口总结
题目
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。 找出满足下述条件的下标对 (i, j)#xff1a; i ! j, abs(i - j) indexDi…作者推荐
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值
本文涉及的基础知识点
C算法滑动窗口总结
题目
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。 找出满足下述条件的下标对 (i, j) i ! j, abs(i - j) indexDiff abs(nums[i] - nums[j]) valueDiff 如果存在返回 true 否则返回 false 。 示例 1 输入nums [1,2,3,1], indexDiff 3, valueDiff 0 输出true 解释可以找出 (i, j) (0, 3) 。 满足下述 3 个条件 i ! j -- 0 ! 3 abs(i - j) indexDiff -- abs(0 - 3) 3 abs(nums[i] - nums[j]) valueDiff -- abs(1 - 1) 0 示例 2 输入nums [1,5,9,1,5,9], indexDiff 2, valueDiff 3 输出false 解释尝试所有可能的下标对 (i, j) 均无法满足这 3 个条件因此返回 false 。 提示 2 nums.length 105 -109 nums[i] 109 1 indexDiff nums.length 0 valueDiff 109
多键二叉树滑动窗口
时间复杂度(nlogn) (i,j)和(j,i)完全相同所以只需要判断一个不是一般性假定ij。我们枚举j看[j-indexDiff,i) 是否存在合法的i。std::multiset setRang 记录nums[j-indexDiff,i)。 [it,ij)是值大于等于nums[j]-valueDiff且小于等于nums[j]valueDiff。 **注意 不能直接ij-it那样的时间复杂是O(n)。 setRang不能直接删除值那样重复值会一起删除。
multiset是多键二叉树由于可能有重复元素所以不能用单键二叉树。
代码
核心代码
class Solution {
public:bool containsNearbyAlmostDuplicate(vectorint nums, int indexDiff, int valueDiff) {std::multisetint setRang;for (int right 0; right nums.size(); right){const int iDelIndex right - indexDiff - 1;if (iDelIndex 0){setRang.erase(setRang.find(nums[iDelIndex]));}auto it setRang.lower_bound(nums[right] - valueDiff);auto ij setRang.upper_bound(nums[right] valueDiff);if (it ! ij){return true;} setRang.emplace(nums[right]);}return false;}
};测试用例 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 indexDiff, valueDiff;{Solution sln;nums { 1, 2, 3, 1 }, indexDiff 3, valueDiff 0;auto res sln.containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff);Assert(true, res);}{Solution sln;nums { 1, 5, 9, 1, 5, 9 }, indexDiff 2, valueDiff 3;auto res sln.containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff);Assert(false, res);}}2023年4月版
class Solution { public: bool containsNearbyAlmostDuplicate(vector nums, int indexDiff, int valueDiff) { std::multiset setHas; for (int i 0; i nums.size(); i) { const int iDelIndex i - indexDiff - 1; if (iDelIndex 0) { auto it setHas.find(nums[iDelIndex]); setHas.erase(it); } auto it1 setHas.lower_bound(nums[i] - valueDiff); auto it2 setHas.upper_bound(nums[i] valueDiff); if (it1 ! it2) { return true; } setHas.emplace(nums[i]); } return false; } };
桶排序算法
时间复杂度(n) 桶排序算法是经典排序算法。 桶大小合适桶中元素大小一定符合条件。这样可以确保桶中只有一个元素如果桶中有两个元素直接返回true。只需要比较当前桶前一个桶后一个桶。 class Solution { public: bool containsNearbyAlmostDuplicate(vector nums, int k, int t) { unordered_mapint, int mp; int n nums.size(); for (int i 0; i n; i) { const int curValue nums[i]; int inx GetBucketIndex(curValue, t 1); if (mp.count(inx)) { return true; } if (mp.count(inx - 1) (abs(curValue - mp[inx - 1]) t)) { return true; } if (mp.count(inx 1) (abs(curValue - mp[inx 1]) t)) { return true; } mp[inx] curValue; if (i k) { const int iEraseIndex GetBucketIndex(nums[i - k ],t1); mp.erase(iEraseIndex); } } return false; } int GetBucketIndex(int value, int iBuckCap) { return value 0 ? (value / iBuckCap) : ((value 1) / iBuckCap - 1); } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 实现。
