【前缀和】【单调栈】LeetCode2281:巫师的总力量和

作者推荐

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

涉及知识点

单调栈
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

作为国王的统治者，你有一支巫师军队听你指挥。
给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：
巫师中 最弱 的能力值。
组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
示例 1：
输入：strength = [1,3,1,2]
输出：44
解释：以下是所有连续巫师组：

  • [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
  • [1,3,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9
  • [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
  • [1,3,1,2] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4
  • [1,3,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4
  • [1,3,1,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4
  • [1,3,1,2] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3
  • [1,3,1,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
  • [1,3,1,2] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
  • [1,3,1,2] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
    所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。
    示例 2：

输入：strength = [5,4,6]
输出：213
解释：以下是所有连续巫师组：

  • [5,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25
  • [5,4,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16
  • [5,4,6] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36
  • [5,4,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36
  • [5,4,6] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40
  • [5,4,6] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
    所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。
    参数范围：
    1 <= strength.length <= 105
    1 <= strength[i] <= 109

单调栈+两个前缀和

时间复杂度: O(n)。

单调栈

枚举各数组的最小值。left 是从右向左第一个小于strength[i]的下标是left，如果不存在left是-1;right是从左向右第一个小于等于strength[i]的下标，如果不存在right为m_c。
如果一个子数组strength[li,ri]的最小值是strength[i]，且strength[i]左边没有和它相等的值。则：
li的取值范围是：(left,i]
ri的取值范围是：[i,right)
我们可以这样计算这些子数组和的和。累加strength[i]它出现的次数。
无论li和ri取值什么，i都在子数组中，所以i出现：(i-left)(right-i)次。
li为left+1时,ri无论取值什么，都包括strength[left+1]
li为left+1和left+2时，ri无论取值什么，都包括strength[left+2]
…

(left,i)中的元素分别出现:right-i次、(right-i)*2、(right-i)*3…

(i,right)中的元素，分别出现：…、(i-left)*2、(i-left)次

前缀和

vPreSum[i] 记录：strength[j]的和，j取值范围[0,i)。
vPreSum2[i]记录：strength[j]*(j+1)的和，j取值范围[0,i)。

代码

核心代码

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(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]。
};

template<class T = long long >
vector<T> CreatePreSum(const vector<int>& nums)
{
	vector<T> preSum;
	preSum.push_back(0);
	for (int i = 0; i < nums.size(); i++)
	{
		preSum.push_back (preSum[i]+ nums[i]);
	}
	return preSum;
}

class Solution {
public:
	int totalStrength(vector<int>& strength) {
		CRangIndex ri(strength, [&](int i1, int i2) {return strength[i1] <= strength[i2]; });
		auto vPreSum = CreatePreSum<C1097Int<>>(strength);
		vector<C1097Int<>> vPreSum2 = { 0 };
		for (int i = 0 ; i < ri.m_c ;  i++ )
		{
			const auto& n = strength[i];
			vPreSum2.emplace_back(vPreSum2.back() + C1097Int<>(n)*(i+1));
		}
		C1097Int<> biRet = 0;
		for (int i = 0; i < ri.m_c; i++)
		{
			const int left = ri.m_vLeft[i];
			const int right = ri.m_vRight[i];
			const int leftLen = i - left;//左边界的可选范围(left,i]
			const int rightLen = right - i;//右边界的可选范围[i,right)
			//计算(left,i)的巫师和
			C1097Int<> leftTotal = vPreSum2[i] - vPreSum2[left + 1] - (vPreSum[i] - vPreSum[left + 1]) * (left+1);
			//计算(i,right)的巫师和
			C1097Int<> rightTotal = (vPreSum[right] - vPreSum[i + 1])*(right+1) - ( vPreSum2[right] - vPreSum2[i + 1] );
			C1097Int<> iTotal = C1097Int<>(strength[i]) * leftLen * rightLen;
			//计算以小标i为最弱力量的子数组
			C1097Int<> cur = leftTotal * rightLen + rightTotal * leftLen + iTotal;
			cur *= strength[i];
			biRet += cur;
		}
		return biRet.ToInt();
	}
};

测试用例

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> strength;
	{
		Solution slu;
		strength = { 2,3,4 };
		auto res = slu.totalStrength(strength);
		Assert(78, res);
	}
	{
		Solution slu;
		strength = { 1 };
		auto res = slu.totalStrength(strength);
		Assert(1, res);
	}
	{
		Solution slu;
		strength = { 1,3 };
		auto res = slu.totalStrength(strength);
		Assert(14, res);
	}
	{
		Solution slu;
		strength = { 1, 3, 1, 2 };
		auto res = slu.totalStrength(strength);
		Assert(44, res);
	}
	{
		Solution slu;
		strength = { 5,4,6 };
		auto res = slu.totalStrength(strength);
		Assert(213, res);
	}

	{
		Solution slu;
		strength.assign(100'000, 1000'000'000);
		auto res = slu.totalStrength(strength);
		Assert(611131623, res);
	}
	
	//CConsole::Out(res);
}

2023年3月版

class Solution {
public:
int totalStrength(vector& strength) {
m_c = strength.size();
vector vSum1(1), vSum2(1);
for (int i = 0; i < m_c; i++)
{
vSum1.push_back(vSum1.back() + strength[i]);
vSum2.push_back(vSum2.back() + (long long)strength[i] * (i + 1));
}
vector vLeft(m_c), vRight(m_c);
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = 0; i < m_c; i++)
{
const int iLessEqualNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i] + 1, LessPairInt) - vValueIndex.begin();
vLeft[i] = (0 == iLessEqualNum) ? -1 : vValueIndex[iLessEqualNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = m_c - 1; i >= 0; i–)
{
const int iLessNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i], LessPairInt) - vValueIndex.begin();
vRight[i] = (0 == iLessNum) ? m_c : vValueIndex[iLessNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}

	 C1097Int llSum = 0;
	 for (int i = 0; i < m_c; i++)
	 {
		 const int iLeftLeft = vLeft[i] + 1;
		 const int iLeftRight = i - 1;
		 const int iRightLeft = i + 1;
		 const int iRightRight = vRight[i] - 1;
		 const int iLeftLen = iLeftRight - iLeftLeft + 1;
		 const int iRightLen = iRightRight - iRightLeft + 1;
		 C1097Int llCurSun = ((long long)iLeftLen + 1)*(iRightLen + 1)*strength[i];
		 C1097Int llLeftSum = 0, llRightSum = 0;
		 if (iLeftLen > 0)
		 {
			 llLeftSum = vSum2[iLeftRight + 1] - vSum2[iLeftLeft] - (vSum1[iLeftRight + 1] - vSum1[iLeftLeft])*iLeftLeft;
			 llLeftSum *= (iRightLen + 1);
		 }
		 if (iRightLen > 0)
		 {
			 llRightSum = (vSum1[iRightRight + 1] - vSum1[iRightLeft])*(iRightRight + 2) - (vSum2[iRightRight + 1] - vSum2[iRightLeft]);
			 llRightSum *= (iLeftLen + 1);
		 }
		 llCurSun += llLeftSum;
		 llCurSun += llRightSum;
		 llSum += llCurSun*strength[i];
	 }
	 return llSum.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++ 实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/263486.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LIGA-Stereo：为基于立体 3D 检测器的学习 LiDAR 几何感知表示

LIGA-Stereo：为基于立体 3D 检测器的学习 LiDAR 几何感知表示

论文地址&#xff1a;https://openaccess.thecvf.com/content/ICCV2021/papers/Guo_LIGA-Stereo_Learning_LiDAR_Geometry_Aware_Representations_for_Stereo-Based_3D_Detector_ICCV_2021_paper.pdf 论文代码&#xff1a;https://github.com/xy-guo/LIGA-Stereo 摘要 基于立…
阅读更多...
（离散数学）格的性质

（离散数学）格的性质

阅读更多...
基于MybatisPlus批量高效插入百万条数据

基于MybatisPlus批量高效插入百万条数据

引言 在JAVA程序开发中&#xff0c;对数据库进行大量数据插入是一个常见的操作&#xff0c;作为一个软件开发工程师&#xff0c;大批量的数据处理是日常工作&#xff0c;如何优化插入性能&#xff0c;提升数据处理效率是对大多数工程师的一个重要考验。本文将围绕逐条插入和批…
阅读更多...
一分钟学会“沉浸式翻译”插件的安装与使用

一分钟学会“沉浸式翻译”插件的安装与使用

一、安装 安装地址&#xff1a;https://immersivetranslate.com/ 选择对应的浏览器进入安装即可 二、简单的翻译使用方法 第一次安装需要先刷新界面才可以达到翻译效果 核心需要修改的地方在以下三个&#xff1a; 第一处&#xff1a;设置翻译服务&#xff0c;免费版的可以直接…
阅读更多...
重温经典struts1之自定义类型转换器及注册的两种方式(Servlet,PlugIn)

重温经典struts1之自定义类型转换器及注册的两种方式(Servlet,PlugIn)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 Struts的ActionServlet接收用户在浏览器发送的请求&#xff0c;并将用户输入的数据&#xff0c;按照FormBean中定义的数据类型&#xff0c;赋值给FormBean中每个变量&a…
阅读更多...
八：爬虫-MySQL基础

八：爬虫-MySQL基础

一&#xff1a;MySQL数据库基础 1.MySQL数据库介绍 MySQL是一个[关系型数据库管理系统]&#xff0c;由瑞典MySQL AB 公司开发&#xff0c;属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一&#xff0c;在 WEB 应用方面&#xff0c;MySQL是最好的 RDBMS (Rela…
阅读更多...
Kafka大数据框架学习攻略：精选Kafka学习资源，助你迅速掌握分布式消息系统！

Kafka大数据框架学习攻略：精选Kafka学习资源，助你迅速掌握分布式消息系统！

介绍&#xff1a;Kafka是一个分布式、支持分区、多副本的基于zookeeper协调的分布式消息系统&#xff0c;可以实时处理大量数据和满足各种需求场景。它是一个基于发布/订阅模式的消息队列&#xff0c;主要应用于大数据实时处理领域&#xff0c;支持消息的发布、订阅、消费和处理…
阅读更多...
2023年12月21日开发正式版v1.2.3更新·本次更新30多个细节优化·完善丰富后台功能·加入演员关联机制

2023年12月21日开发正式版v1.2.3更新·本次更新30多个细节优化·完善丰富后台功能·加入演员关联机制

2023年12月21日开发正式版v1.2.3更新本次更新30多个细节优化完善丰富后台功能加入演员关联机制 产品简介 安卓苹果PCH5四端&#xff0c;蜻蜓z暗影版的衍生级版本&#xff0c;2023年优雅草蜻蜓z冬季雪花限定版&#xff0c;不仅继承了蜻蜓z的精良功能&#xff0c;还特色增加了弹…
阅读更多...
[LitCTF 2023]PHP是世界上最好的语言！！

[LitCTF 2023]PHP是世界上最好的语言！！

[LitCTF 2023]PHP是世界上最好的语言&#xff01;&#xff01; wp 进入页面&#xff0c;发现左边有输入框&#xff0c;下面有 RUN CODE 字样&#xff0c;估计是可以执行命令的。 执行 PHP 代码测试 <?php print(1); ?>将 PHP 一句话木马写入文件 为了蚁剑能连上&am…
阅读更多...
通过几个基本概念说一下为什么openGauss是当下之选？

通过几个基本概念说一下为什么openGauss是当下之选？

Database、Schema、User都是数据库的基本概念&#xff0c;SQL标准中也有明确规范。但不同数据库的具体实现也不尽相同&#xff0c;有些甚至大相径庭。这就导致用户在做国产化选型和数据库迁移时可能会遇到种种困难。本文从这几个基本概念展开&#xff0c;说说为什么openGauss系…
阅读更多...
uniapp实战 -- 个人信息维护（含选择图片 uni.chooseMedia，上传文件 uni.uploadFile，获取和更新表单数据）

uniapp实战 -- 个人信息维护（含选择图片 uni.chooseMedia，上传文件 uni.uploadFile，获取和更新表单数据）

效果预览 相关代码 页面–我的 src\pages\my\my.vue <!-- 个人资料 --><view class"profile" :style"{ paddingTop: safeAreaInsets!.top px }"><!-- 情况1&#xff1a;已登录 --><view class"overview" v-if"membe…
阅读更多...
docker数据卷数据卷容器

docker数据卷数据卷容器

前言 今天调休在家&#xff0c;随便玩玩&#xff0c;简单做下学习记录 1. 数据卷特点 数据卷在容器启动时初始化&#xff0c;如果容器使用的镜像在挂载点包含了数据&#xff0c;这些数据会被拷贝到新初始化的数据卷中数据卷可以在容器之间共享和重用可以对数据卷里的内容直接…
阅读更多...
【Linux】编辑、查看和搜索文件

【Linux】编辑、查看和搜索文件

大多数 Linux 发行版不包含真正的 vi;而是自带一款高级替代版本&#xff0c;叫做 vim(它是“vi improved”的简写)由 Bram Moolenaar 开发的&#xff0c;vim 相对于传统的 Unix vi 来说&#xff0c;取得了实质性进步。 启动和退出 vim 使用vim可以启动&#xff0c;如命令行输…
阅读更多...
电脑文件msvcp140.dll丢失该怎么解决？靠谱的msvcp140.dll修复方法

电脑文件msvcp140.dll丢失该怎么解决？靠谱的msvcp140.dll修复方法

面对计算机系统报告的msvcp140.dll文件丢失警报&#xff0c;这个问题可能会阻碍依赖此特定动态链接库(DLL)的一些程序的正常启动和运行。解决msvcp140.dll文件丢失的问题对于保障相关应用程序能够无障碍操作非常关键&#xff0c;并且这还是确保计算机系统保持高效稳定运行的必要…
阅读更多...
华为gre隧道全部跑静态路由

华为gre隧道全部跑静态路由

最终实现&#xff1a; 1、pc1能用nat上网ping能pc3 2、pc1能通过gre访问pc2 3、全部用静态路由做&#xff0c;没有用ospf&#xff0c;如果要用ospf&#xff0c;那么两边除了路由器上跑ospf&#xff0c;核心交换机也得用ospf r2配置&#xff1a; acl number 3000 rule 5 deny…
阅读更多...
Java设计模式之单例模式以及如何防止通过反射破坏单例模式

Java设计模式之单例模式以及如何防止通过反射破坏单例模式

单例模式 单例模式使用场景 ​ 什么是单例模式&#xff1f;保障一个类只能有一个对象&#xff08;实例&#xff09;的代码开发模式就叫单例模式 ​ 什么时候使用&#xff1f; 工具类&#xff01;&#xff08;一种做法&#xff0c;所有的方法都是static&#xff0c;还有一种单…
阅读更多...
Notepad++如果同一个窗口，打开了很多文件，需另开一个窗口

Notepad++如果同一个窗口，打开了很多文件，需另开一个窗口

如果一个窗口已经这么多了&#xff0c;需要另外再一个 这里打开
阅读更多...
效果图云渲染是什么意思？如何渲染出照片级别的效果图?

效果图云渲染是什么意思？如何渲染出照片级别的效果图?

​在当前的建筑规划、室内装修以及电影视效制作等行业内&#xff0c;制作高质量的效果图起着至关重要的作用&#xff0c;因为它能够给予观众或客户极为逼真和吸引人的视觉体验。在此篇文章中&#xff0c;我们将深入了解什么是云端效果图渲染&#xff0c;并探讨如何运用Renderbu…
阅读更多...
C#中如何稳定精确地每隔5ms执行某个函数？

C#中如何稳定精确地每隔5ms执行某个函数？

C#中如何稳定精确地每隔5ms执行某个函数&#xff1f; 在开始前我有一些资料&#xff0c;是我根据自己从业十年经验&#xff0c;熬夜搞了几个通宵&#xff0c;精心整理了一份「C#的资料从专业入门到高级教程工具包」&#xff0c;点个关注&#xff0c;全部无偿共享给大家&#xf…
阅读更多...
技术丨 浅谈以太网系统级刷写测试

技术丨 浅谈以太网系统级刷写测试

在研发阶段&#xff0c;我们一般将ECU直连至刷写上位机进行软件更新&#xff0c;但在整车环境中&#xff0c;各ECU之间通过线束连接在一起&#xff0c;如果此时想对某个单独的样件进行软件更新&#xff0c;把零件拆下来再接到上位机上进行软件更新是不现实的。 作为测试工程师…
阅读更多...
最新文章

Copyright @ 2022~2023