当前位置:网站首页>【Leetcode】2104. Sum of Subarray Ranges
【Leetcode】2104. Sum of Subarray Ranges
2022-08-09 22:01:00 【记录算法题解】
题目地址:
https://leetcode.com/problems/sum-of-subarray-ranges/
给定一个长 n n n数组 A A A,求 ∑ l ≤ r ( max A [ l : r ] − min A [ l : r ] ) \sum_{l\le r}(\max A[l:r]-\min A[l:r]) ∑l≤r(maxA[l:r]−minA[l:r])。
参考https://blog.csdn.net/qq_46105170/article/details/109734115。代码如下:
class Solution {
public:
using LL = long long;
LL subArrayRanges(vector<int>& nums) {
auto less = [](int& x, int& y) {
return x <= y; };
auto more = [](int& x, int& y) {
return x >= y; };
return calc(nums, more) - calc(nums, less);
}
LL calc(vector<int>& v, bool (*comp)(int&, int&)) {
stack<int> stk;
LL res = 0;
for (int i = 0; i < v.size(); i++) {
while (stk.size() && comp(v[i], v[stk.top()])) {
int idx = stk.top(); stk.pop();
int l = idx - (stk.size() ? stk.top() : -1), r = i - idx;
res += (LL)v[idx] * l * r;
}
stk.push(i);
}
while (stk.size()) {
int idx = stk.top(); stk.pop();
int l = idx - (stk.size() ? stk.top() : -1), r = v.size() - idx;
res += (LL)v[idx] * l * r;
}
return res;
}
};
时空复杂度 O ( n ) O(n) O(n)。
边栏推荐
- 注意力引导网络用于视网膜图像分割
- 国内手机厂商曾为它大打出手,如今它却最先垮台……
- Let's talk about what DDL, DML, DQL and DCL are in SQL statements
- Basic operations of openGauss database (super detailed)
- How do task flow executors work?
- OFDM 十六讲 7 - Inter-Symbol-Interference
- 好未来,想成为第二个新东方
- mysql multi-table left link query
- Socket发送缓冲区接收缓冲区快问快答
- MySQL——JDBC
猜你喜欢
随机推荐
【服务器数据恢复】SAN LUN映射出错导致文件系统数据丢失的数据恢复案例
2022年中国第三方证券APP创新专题分析
A. Common Prefixes
R语言ggplot2可视化:使用ggpubr包的ggscatter函数可视化散点图、使用scale_x_continuous函数的breaks参数指定X轴的断点的个数(设置参数n)
typedef和#define的花里胡哨的用法
【技术分享】SLA(服务等级协议)原理与配置
【Apifox】为什么如此受青睐,此篇文章和大家分享
Redis
leetcode:320.列举单词的全部缩写
JuiceFS 在多云存储架构中的应用 | 深势科技分享
R语言ggstatsplot包grouped_ggscatterstats函数可视化分组散点图、并添加假设检验结果(包含样本数、统计量、效应大小及其置信区间、显著性、组间两两比较、贝叶斯假设)
为什么这么多人都想当产品经理?
[Microservice~Nacos] Nacos service provider and service consumer
web 面试高频考点 —— 性能优化篇(手写防抖、手写节流、XXS攻击、XSRF攻击)
mysql 、pg 查询日期处理
信息系统项目管理师---第十一章项目风险管理历年考题
navicat 快捷键
leetcode:332. 重新安排行程
C. Binary String Reconstruction
A1. Prefix Flip (Easy Version)