【单调栈】LeetCode:2818操作使得分最大

2023-12-23 08:15
文章标签 leetcode 操作 最大 单调 2818

本文主要是介绍【单调栈】LeetCode:2818操作使得分最大，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

map|动态规划|单调栈|LeetCode975:奇偶跳

涉及知识点

单调栈

题目

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。
一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：
选择一个之前没有选过的 非空 子数组 nums[l, …, r] 。
从 nums[l, …, r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
将你的分数乘以 x 。
nums[l, …, r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。
一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。
请你返回进行至多 k 次操作后，可以得到的 最大分数 。
由于答案可能很大，请你将结果对 109 + 7 取余后返回。
示例 1：
输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：进行以下操作可以得到分数 81 ：

  • 选择子数组 nums[2, …, 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
  • 选择子数组 nums[2, …, 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
    81 是可以得到的最高得分。
    示例 2：
    输入：nums = [19,12,14,6,10,18], k = 3
    输出：4788
    解释：进行以下操作可以得到分数 4788 ：
  • 选择子数组 nums[0, …, 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
  • 选择子数组 nums[5, …, 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
  • 选择子数组 nums[2, …, 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 342 * 14 = 4788 。
    4788 是可以得到的最高的分。
    参数范围：
    1 <= nums.length == n <= 105
    1 <= nums[i] <= 105
    1 <= k <= min(n * (n + 1) / 2, 109)

单调栈

时间复杂度😮(nlogn)
静态变量vPrime 记录所有质数。
vPriCount 记录nums各数的质量分数。vPriCount也可以弄成静态成员变量。
我们枚举各子数组的最大质量分数，如果有多个最大质量分数，取下标最小的。即：
left为从右向左第一个大于等于vPriCount[i]的下标，不存在为-1。
right为从左向右第一个大于vPriCount[i]的下标，不存在为m_c。
子数组(li,ri)就是符合条件的子数组，li取值范围(left,i]，ri取值范围[i,right)。
我们按的nums[i]降序操作 最大质量分数为vPriCount[i]的子数组。

代码

核心代码

class CRangIndex
{
public:template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurIndexCmpStackTopIndex){m_c = nums.size();m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top()))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}int m_c;vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};vector<int> CreatePrime(int iMax)
{vector<int> vPrime = { 2 };for (int i = 3; i <= iMax; i++){bool b = true;for (const auto& n : vPrime){if (0 == i % n){b = false;break;}}if (b){vPrime.emplace_back(i);}}return vPrime;
}template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vPriCount;{static vector<int> vPrime = CreatePrime(1000 * 100);for (const auto& n : nums){int tmp = n;int iNum = 0;for (const auto& pr : vPrime){if (pr * pr > tmp){break;}if (0 == tmp % pr){while (0 == tmp % pr){tmp /= pr;}iNum++;}}vPriCount.emplace_back(iNum + (tmp > 1));}}CRangIndex ri(vPriCount, [&](int i1, int i2) {return vPriCount[i1] > vPriCount[i2]; });std::multimap<int, int, greater<int>> mValueIndex;for (int i = 0; i < ri.m_c; i++){mValueIndex.emplace(nums[i], i);}C1097Int<> biRet=1;for (const auto& [value, i] : mValueIndex){const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);const long long llOpeCount = min((long long)k, llSubArrCount);biRet *= C1097Int<>(value).pow(llOpeCount);k -= llOpeCount;if (0 == k){break;}}return biRet.ToInt();}int m_c;
};

测试用例

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 slu;nums = { 8, 3, 9, 3, 8 };k = 2;auto res = slu.maximumScore(nums, k);Assert(81, res);}{Solution slu;nums = { 19,12,14,6,10,18 };k = 3;auto res = slu.maximumScore(nums, k);Assert(4788, res);}//CConsole::Out(res);
}

2023年8月

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(int n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};template<int MOD = 1000000007>
int operator+(int iData, const C1097Int<MOD>& int1097)
{int iRet = int1097.operator+(C1097Int<MOD>(iData)).ToInt();return iRet;
}template<int MOD = 1000000007>
int& operator+=(int& iData, const C1097Int<MOD>& int1097)
{iData = int1097.operator+(C1097Int<MOD>(iData)).ToInt();return iData;
}template<int MOD = 1000000007>
int operator*(int iData, const C1097Int<MOD>& int1097)
{int iRet = int1097.operator*(C1097Int(iData)).ToInt();return iRet;
}template<int MOD = 1000000007>
int& operator*=(int& iData, const C1097Int<MOD>& int1097)
{iData = int1097.operator*(C1097Int(iData)).ToInt();return iData;
}class Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vScore;for ( int n : nums){int iScore = 0;for (int i = 2; i * i <= n; i++){if (0 != n % i){continue;}iScore++;while (0 == n % i){n /= i;}}if (n > 1){iScore++;}vScore.emplace_back(iScore);}stack<int> sta;vector<int> vLeft(m_c), vRight(m_c, m_c);for (int i = 0 ; i < m_c ; i++ ){while (sta.size() && (vScore[sta.top()] < vScore[i])){vRight[sta.top()] = i;sta.pop();}vLeft[i] = sta.size() ? sta.top() : -1;sta.emplace(i);			}std::map<int, long long,std::greater<int>> mValueNum;for (int i = 0; i < m_c; i++){mValueNum[nums[i]] += (i - vLeft[i])*(long long)(vRight[i] - i);}C1097Int<> biRet = 1;while (k > 0){for (auto it : mValueNum){long long llMulMul = min((long long)k, it.second);k -= llMulMul;auto cur = C1097Int<>(it.first).pow((int)llMulMul);biRet *= cur;}}return biRet.ToInt();}int m_c;
};

使用封装类后

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class CRangIndex
{
public:template<class _Pr>CRangIndex(int iVectorSize, _Pr CurIndexCmpStackTopIndex){m_c = iVectorSize;m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top()))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue){m_c = nums.size();m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurValueCmpStackTopValue(nums[i], nums[sta.top()]))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}int m_c;vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};vector<int> CreatePrime(int iMax)
{vector<int> vPrime = { 2 };for (int i = 3; i <= iMax; i++){bool b = true;for (const auto& n : vPrime){if (0 == i % n){b = false;break;}}if (b){vPrime.emplace_back(i);}}return vPrime;
}
class Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vPriCount;{static vector<int> vPrime = CreatePrime(1000 * 100);for (const auto& n : nums){int tmp = n;int iNum = 0;for (const auto& pr : vPrime){if (pr * pr > tmp){break;}if (0 == tmp % pr){while (0 == tmp % pr){tmp /= pr;}iNum++;}}vPriCount.emplace_back(iNum + (tmp > 1));}}CRangIndex ri(vPriCount, std::greater<>());std::multimap<int, int, greater<int>> mValueIndex;for (int i = 0; i < ri.m_c; i++){mValueIndex.emplace(nums[i], i);}C1097Int<> biRet=1;for (const auto& [value, i] : mValueIndex){const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);const long long llOpeCount = min((long long)k, llSubArrCount);biRet *= C1097Int<>(value).pow(llOpeCount);k -= llOpeCount;if (0 == k){break;}}return biRet.ToInt();}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++ 实现。

这篇关于【单调栈】LeetCode:2818操作使得分最大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/527329。

相关文章

Python使用python-pptx自动化操作和生成PPT

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看
阅读更多...
MySQL 数据库表操作完全指南:创建、读取、更新与删除实战

MySQL 数据库表操作完全指南:创建、读取、更新与删除实战

《MySQL数据库表操作完全指南:创建、读取、更新与删除实战》本文系统讲解MySQL表的增删查改（CURD）操作,涵盖创建、更新、查询、删除及插入查询结果,也是贯穿各类项目开发全流程的基础数据交互原... 目录mysql系列前言一、Create(创建)并插入数据1.1 单行数据 + 全列插入1.2 多行数据
阅读更多...
MySQL 临时表与复制表操作全流程案例

MySQL 临时表与复制表操作全流程案例

《MySQL临时表与复制表操作全流程案例》本文介绍MySQL临时表与复制表的区别与使用,涵盖生命周期、存储机制、操作限制、创建方法及常见问题,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随小... 目录一、mysql 临时表（一）核心特性拓展（二）操作全流程案例1. 复杂查询中的临时表应用2. 临时
阅读更多...
MySQL 数据库表与查询操作实战案例

MySQL 数据库表与查询操作实战案例

《MySQL数据库表与查询操作实战案例》本文将通过实际案例,详细介绍MySQL中数据库表的设计、数据插入以及常用的查询操作,帮助初学者快速上手,感兴趣的朋友跟随小编一起看看吧... 目录mysql 数据库表操作与查询实战案例项目一：产品相关数据库设计与创建一、数据库及表结构设计二、数据库与表的创建项目二：员
阅读更多...
Java Stream流以及常用方法操作实例

Java Stream流以及常用方法操作实例

《JavaStream流以及常用方法操作实例》Stream是对Java中集合的一种增强方式,使用它可以将集合的处理过程变得更加简洁、高效和易读,：本文主要介绍JavaStream流以及常用方法... 目录一、Stream流是什么？二、stream的操作2.1、stream流创建2.2、stream的使用2.
阅读更多...
MySQL数据类型与表操作全指南( 从基础到高级实践)

MySQL数据类型与表操作全指南( 从基础到高级实践)

《MySQL数据类型与表操作全指南(从基础到高级实践)》本文详解MySQL数据类型分类（数值、日期/时间、字符串）及表操作（创建、修改、维护）,涵盖优化技巧如数据类型选择、备份、分区,强调规范设计与... 目录mysql数据类型详解数值类型日期时间类型字符串类型表操作全解析创建表修改表结构添加列修改列删除列
阅读更多...
python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
Python操作PDF文档的主流库使用指南

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
MySQL 强制使用特定索引的操作

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2