南宁营销网站建设,一流的网站建设公司,南宁网站建设价格,网站建设进度总结作者推荐
利用广度优先或模拟解决米诺骨牌
题目
给你一个整数数组 nums #xff08;下标从 0 开始#xff09;和一个整数 k 。 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], …, nums[j]) * (j - i 1) 。一个 好 子数组的两个端点下标需要满足 i k 下标从 0 开始和一个整数 k 。 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], …, nums[j]) * (j - i 1) 。一个 好 子数组的两个端点下标需要满足 i k j 。 请你返回 好 子数组的最大可能 分数 。 示例 1 输入nums [1,4,3,7,4,5], k 3 输出15 解释最优子数组的左右端点下标是 (1, 5) 分数为 min(4,3,7,4,5) * (5-11) 3 * 5 15 。 示例 2 输入nums [5,5,4,5,4,1,1,1], k 0 输出20 解释最优子数组的左右端点下标是 (0, 4) 分数为 min(5,5,4,5,4) * (4-01) 4 * 5 20 。 参数 1 nums.length 105 1 nums[i] 2 * 104 0 k nums.length
分析
时间复杂度
O(n)。
步骤
一寻找nums[i]的右边界数组边界或从左向右第一个小于nums[i]的数。如果i1小于i2且nums[i1] nums[i2]则i1淘汰了i2淘汰后:i降序nums[i]升序。 二寻找nums[i]的左边界数组左边界或从右向左第一个小于nums[i]的数。 三左开右开区间(vLeft[i],vRight[i]) 就是以nums[i]为最小值的区间。如果k在这个区间则更新返回值。
代码
核心代码
class Solution { public: int maximumScore(vector nums, int k) { m_c nums.size(); vector vRight(m_c, m_c); { vector vIndexs; for (int i m_c-1 ; i 0 ; i-- ) { while (vIndexs.size() (nums[vIndexs.back()] nums[i])) { vIndexs.pop_back(); } if (vIndexs.size()) { vRight[i] vIndexs.back(); } vIndexs.emplace_back(i); } } vector vLeft(m_c, -1); { vector vIndexs; for (int i 0; i m_c; i) { while (vIndexs.size() (nums[vIndexs.back()] nums[i])) { vIndexs.pop_back(); } if (vIndexs.size()) { vLeft[i] vIndexs.back(); } vIndexs.emplace_back(i); } } int iRet 0; for (int i 0; i m_c; i) { if ((k vLeft[i]) (k vRight[i])) { iRet max(iRet, nums[i] * (vRight[i] - vLeft[i] - 1)); std::cout i nums[i]: nums[i] vLeft[i] vRight[i] std::endl; } } return iRet; } int m_c; };
优化寻找边界循环一次
左边界数组边界或小于nums[i]右边界数组边界或小于等于nums[i]
改变规则后寻找左边界淘汰vIndexs时说明i是vIndexs.back()的第一个小于等于的数也就是右边界。
题外话
解法一会造成重复本题是求最大值重复不会影响结果。求和就会有影响了。
比如{1,1}
解法一解法二i0{1,1}{1}i1{1,1}{1,1}
拆开后
解法一{1}{1}{1,1}{1,1}解法二{1}{1,1}{1}
代码
class Solution {
public:int maximumScore(vectorint nums, int k) {m_c nums.size();vectorint vRight(m_c, m_c);vectorint vLeft(m_c, -1);vectorint vIndexs;for (int i 0; i m_c; i){while (vIndexs.size() (nums[vIndexs.back()] nums[i])){vRight[vIndexs.back()] i;vIndexs.pop_back();}if (vIndexs.size()){vLeft[i] vIndexs.back();}vIndexs.emplace_back(i);}int iRet 0;for (int i 0; i m_c; i){if ((k vLeft[i]) (k vRight[i])){iRet max(iRet, nums[i] * (vRight[i] - vLeft[i] - 1));std::cout i nums[i]: nums[i] vLeft[i] vRight[i] std::endl;}}return iRet;}int m_c;
};2023年3月旧代码
class Solution { public: int maximumScore(vector nums, int k) { m_c nums.size(); vectorstd::pairint, int staLeft,staRight; { for (int i 0; i k; i) { while (staLeft.size() (staLeft.back().first nums[i])) { staLeft.pop_back(); } staLeft.emplace_back(nums[i], i); } } { for (int i nums.size() - 1; i k; i–) { while (staRight.size() (staRight.back().first nums[i])) { staRight.pop_back(); } staRight.emplace_back(nums[i], i); } } auto CmpFun [](const std::pairint, int p, int iCmp) {return p.first iCmp; }; int iMaxRet 0 ; for (int iValue 1; iValue nums[k]; iValue) { auto it std::lower_bound(staLeft.begin(), staLeft.end(), iValue, CmpFun); int iLeft (staLeft.begin() it) ? -1 : (–it)-second; auto it2 std::lower_bound(staRight.begin(), staRight.end(), iValue, CmpFun); int iRight (staRight.begin() it2) ? m_c : (–it2)-second; iMaxRet max(iMaxRet, iValue* (iRight - iLeft - 1)); } return iMaxRet; } 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
