LeetCode-2104 子数组范围和
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sum-of-subarray-ranges
题目描述
给你一个整数数组 nums 。nums 中,子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1:
输入:nums = [1,2,3]
输出:4
解释:nums 的 6 个子数组如下所示:
[1],范围 = 最大 - 最小 = 1 - 1 = 0
[2],范围 = 2 - 2 = 0
[3],范围 = 3 - 3 = 0
[1,2],范围 = 2 - 1 = 1
[2,3],范围 = 3 - 2 = 1
[1,2,3],范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
示例 2:
输入:nums = [1,3,3]
输出:4
解释:nums 的 6 个子数组如下所示:
[1],范围 = 最大 - 最小 = 1 - 1 = 0
[3],范围 = 3 - 3 = 0
[3],范围 = 3 - 3 = 0
[1,3],范围 = 3 - 1 = 2
[3,3],范围 = 3 - 3 = 0
[1,3,3],范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
示例 3:
输入:nums = [4,-2,-3,4,1]
输出:59
解释:nums 中所有子数组范围的和是 59
提示:
1 <= nums.length <= 1000
-109 <= nums[i] <= 109
解题思路
首先看数据范围,可以通过暴力法来做,遍历子数组,分别求出最大值最小值然后求和,时间复杂度是O(n2)
还有一种巧妙的方法可以将时间复杂度压缩到O(n)。
对于第i个数ai,如果左边第一个比他小的数下标为left,第一个比他小的数下标位right,那么(left,right)中所有的子数组最小值都是ai,在(left,right)中共有(right - i) * (i - left) 个子数组,那么(left, right)范围内子数组最小值的和为(right - i) * (i - left) * ai,同理可以求出(left, right)范围内子数组最大值的和,两个相减就可以求出(left, right)范围内的范围和。
问题转化为了如何第i个数左边小值和大值及右边的小值和大值,使用单调栈一次遍历便可以分别求得这四个值,并且用vector将下标存起来。
代码展示
暴力法:
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long ret = 0;
for (int i = 0; i < n; i++) {
int minVal = INT_MAX, maxVal = INT_MIN;
for (int j = i; j < n; j++) {
minVal = min(minVal, nums[j]);
maxVal = max(maxVal, nums[j]);
ret += maxVal - minVal;
}
}
return ret;
}
};
单调栈+数学:
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long ret = 0;
vector<int> viLeftMin(n), viRightMin(n), viLeftMax(n), viRightMax(n);
stack<int> siMax, siMin;
for(int i = 0; i < n; i++)
{
while(!siMin.empty() && nums[siMin.top()] > nums[i])
siMin.pop();
viLeftMin[i] = siMin.empty()? -1: siMin.top();
siMin.push(i); while(!siMax.empty() && nums[siMax.top()] <= nums[i])
siMax.pop();
viLeftMax[i] = siMax.empty()? -1: siMax.top();
siMax.push(i);
}
siMax = stack<int>();
siMin = stack<int>();
for(int i = n - 1; i >= 0; i--)
{
while(!siMin.empty() && nums[siMin.top()] >= nums[i])
siMin.pop();
viRightMin[i] = siMin.empty()? n: siMin.top();
siMin.push(i); while(!siMax.empty() && nums[siMax.top()] < nums[i])
siMax.pop();
viRightMax[i] = siMax.empty()? n: siMax.top();
siMax.push(i);
} for(int i = 0; i < n; i++)
{
ret += ((((long long)viRightMax[i] - i) * (i - viLeftMax[i])) - (((long long)viRightMin[i] - i) * (i - viLeftMin[i])))* nums[i];
}
return ret;
}
};
运行结果
最新文章
- git学习之branch分支
- My SQL的内连接,外链接查询
- goalng 发布的版本中自动加上 git revision
- jquery------导入jquery.2.2.3.min.js
- [HDOJ1231]最大连续子序列
- php 提交保存成功页面 倒计时 跳转
- iOS之FMDB 转载
- Runtime 函数 Swizzling 改变OC方法的调度顺序
- uva 11437 - Triangle Fun
- Android的logcat命令详解
- LeetCode &; Q414-Third Maximum Number-Easy
- [Javascript]网页链接加上时间戳防止串用户
- Linux基础之常用命令整理(一)
- zabbix添加自定义监控项目
- Alpha冲刺! Day5 - 砍柴
- PowerShell Gallery
- MariaDB 视图与触发器(11)
- k8s相关文档
- 读论文Machine Learning for Improved Diagnosis and Prognosis in Healthcare
- 添加sqljdbc4的maven依赖
热门文章
- 三道MISC的writeup
- [opencv]一些重配遇到的问题(只针对我自己的电脑)
- 三个小任务掌握List、Set、Map
- f-strings: Python字符串处理的瑞士军刀
- vue 引入vant 上传图片oss处理
- Hadoop详解(04-1) - 基于hadoop3.1.3配置Windows10本地开发运行环境
- python之路52 ORM查询、ORM事务、查询优化、常用字段及参数、ajax方法
- Linux操作系统导学专栏(一)——专栏要讲些什么?
- 【C++ 数据结构:链表】二刷LeetCode707设计链表
- Unity_UIWidgets新手入门