广东建设注册中心网站,网页qq邮箱怎么在手机下文件怎么打开wordpress,网站建设费分多少期摊销,上海建站模板厂家作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调栈
题目
给你一个整数数组 nums 和一个整数 threshold 。 找到长度为 k 的 nums 子数组#xff0c;满足数组中 每个 元素都 大于 threshold / k 。 请你返回满足要求的 任意 子数组的 大小 。如果没有这…作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调栈
题目
给你一个整数数组 nums 和一个整数 threshold 。 找到长度为 k 的 nums 子数组满足数组中 每个 元素都 大于 threshold / k 。 请你返回满足要求的 任意 子数组的 大小 。如果没有这样的子数组返回 -1 。 子数组 是数组中一段连续非空的元素序列。 示例 1 输入nums [1,3,4,3,1], threshold 6 输出3 解释子数组 [3,4,3] 大小为 3 每个元素都大于 6 / 3 2 。 注意这是唯一合法的子数组。 示例 2 输入nums [6,5,6,5,8], threshold 7 输出1 解释子数组 [8] 大小为 1 且 8 7 / 1 7 。所以返回 1 。 注意子数组 [6,5] 大小为 2 每个元素都大于 7 / 2 3.5 。 类似的子数组 [6,5,6] [6,5,6,5] [6,5,6,5,8] 都是符合条件的子数组。 所以返回 2, 3, 4 和 5 都可以。 提示 1 nums.length 105 1 nums[i], threshold 109
枚举子数组的最小值
以nums[i]为最小值的左边界是从右向左第一个小于nums[i]的数假定其下标为left。如果不存在,left为-1。 以nums[i]为最小值的右边界是从左向右第一个小于等于nums[i]的数假定其下标为right。如果不存在,right为m_c。 则nums(left,right)是以nums[i]为最小值的最长子数组。显然相同最小值子数组越长越容易符合题目。只需验证最长子数组。
代码
核心代码
class Solution {
public:int validSubarraySize(vectorint nums, int threshold) {m_c nums.size();vectorint vLeft(m_c, -1), vRight(m_c, m_c);//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。stackint sta;for (int i 0; i m_c; i){while (sta.size() (nums[sta.top()] nums[i])){vRight[sta.top()] i;sta.pop();}if (sta.size()){vLeft[i] sta.top();}sta.emplace(i);}for (int i 0; i m_c; i){const int k vRight[i] - vLeft[i] - 1;if ((k 0) (nums[i] threshold / k)){return k;}}return -1;}int m_c;
};测试用例
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 threshold;{Solution slu;nums { 1, 3, 4, 3, 1 }, threshold 6;auto res slu.validSubarraySize(nums, threshold);Assert(3, res);}{Solution slu;nums { 6,5,6,5,8 }, threshold 7;auto res slu.validSubarraySize(nums, threshold);//Assert(1, res);}//CConsole::Out(res);
}2023年3月版
bool Less(const std::pairint, int p, int iData) { return p.first iData; }
class Solution { public: int validSubarraySize(vector nums, int threshold) { m_c nums.size(); vector vLeft(m_c), vRight(m_c); { vectorpairint, int vStack; for (int i 0; i m_c; i) { int iNum std::lower_bound(vStack.begin(), vStack.end(), nums[i], Less) - vStack.begin(); if (0 iNum) { vLeft[i] -1; } else { vLeft[i] vStack[iNum - 1].second; } while (vStack.size() (nums[i] vStack.back().first)) { vStack.pop_back(); } vStack.emplace_back(nums[i], i); } } { vectorpairint, int vStack; for (int i m_c - 1; i 0;i–) { int iNum std::lower_bound(vStack.begin(), vStack.end(), nums[i]1, Less) - vStack.begin(); if (0 iNum) { vRight[i] m_c; } else { vRight[i] vStack[iNum - 1].second; } while (vStack.size() (nums[i] vStack.back().first)) { vStack.pop_back(); } vStack.emplace_back(nums[i], i); } } for (int i 0; i m_c; i) { const int len vRight[i] - vLeft[i] - 1; if (nums[i] threshold / len) { return len; } } return -1; } int m_c; };
2023年7月版
class Solution { public: int validSubarraySize(vector nums, int threshold) { m_c nums.size(); vector vLeft(m_c), vRight(m_c); {//计算左边的长度 stackpairint, int staValueIndex; for (int i 0; i m_c; i) { while (staValueIndex.size() (staValueIndex.top().first nums[i])) { staValueIndex.pop(); } vLeft[i] staValueIndex.empty() ? i : (i - staValueIndex.top().second - 1); staValueIndex.emplace(nums[i], i); } } {//计算右边的长度 stackpairint, int staValueIndex; for (int i m_c-1 ; i 0 ; i-- ) { while (staValueIndex.size() (staValueIndex.top().first nums[i])) { staValueIndex.pop(); } vRight[i] staValueIndex.empty() ? m_c-1-i : ( staValueIndex.top().second - i - 1); staValueIndex.emplace(nums[i], i); } } int iRet -1; for (int i 0; i m_c; i) { const int len vLeft[i] vRight[i]1; const int iNeedK threshold / nums[i] 1; if (len iNeedK){iRet max(iRet, len);}}return iRet;
}
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 实现。
