Loading [MathJax]/jax/input/TeX/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 2104. 子数组范围和(单调栈)

LeetCode 2104. 子数组范围和(单调栈)

作者头像
Michael阿明
发布于 2022-01-07 02:48:58
发布于 2022-01-07 02:48:58
32500
代码可运行
举报
运行总次数:0
代码可运行

文章目录

1. 题目

给你一个整数数组 nums 。nums 中,子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 nums 中 所有 子数组范围的 和 。

子数组是数组中一个连续 非空 的元素序列。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例 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
-10^9 <= nums[i] <= 10^9

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sum-of-subarray-ranges 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 单调栈,获取每个数字作为最大或者最小的左右极限位置
  • 单独考虑每个数字可以作为最大值或者最小值的次数,到左右极限位置处的个数相乘种组合
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        def getRange(nums, neg):
            nums_ = copy.deepcopy(nums)
            if neg:
                for i in range(len(nums)):
                    nums_[i] = -nums_[i] # 找最小值的左右区间,取个负数,逻辑跟正数一样
            L, R = list(range(len(nums))), list(range(len(nums)))
            q = []
            for i in range(len(nums)):
                while len(q) and nums_[q[-1]] < nums_[i]:
                    q.pop()
                L[i] = q[-1]+1 if len(q) else 0
                q.append(i)
            q = []
            for i in reversed(range(len(nums))):
                while len(q) and nums_[q[-1]] <= nums_[i]:
                    q.pop() # 注意上下只能有一个 =R[i] = q[-1]-1 if len(q) else (len(nums)-1)
                q.append(i)
            return L, R
        L1, R1 = getRange(nums, neg=False)
        L2, R2 = getRange(nums, neg=True)
        ans = 0
        for i in range(len(nums)):
            # print(L1[i], R1[i], L2[i], R2[i])
            ans += (R1[i]-i+1)*(i-L1[i]+1)*nums[i]-(R2[i]-i+1)*(i-L2[i]+1)*nums[i]
        return ans

140 ms 15.2 MB Python3


我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/12/12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode笔记:Biweekly Contest 46 比赛记录
我最初的想法是先统计各个字符出现的次数,然后进行统计考察,但是遇到了困难,最后还是直接给出了最暴力的枚举法进行解答的,后续看看有没有更好的解题思路吧……
codename_cys
2021/03/25
2410
Leetcode 1-10
常规方法:使用双重循环,第一重从左往右固定索引,计算需要查找的结果,第二层循环从固定索引出发依次向右查找第一层计算的结果。时间复杂度\(O(n^2)\), 空间复杂度\(O(1)\).
努力努力再努力F
2019/05/08
5290
【综合笔试题】难度 2/5,简单且经典面试题
给定两个大小相等的数组 nums1 和 nums2,nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
宫水三叶的刷题日记
2023/02/27
3310
LeetCode 862. 和至少为 K 的最短子数组(前缀和+deque单调栈)
类似题目: LeetCode 560. 和为K的子数组(前缀和差分) LeetCode 523. 连续的子数组和(求余 哈希) LeetCode 974. 和可被 K 整除的子数组(哈希map)
Michael阿明
2020/07/13
4730
LeetCode笔记:Biweekly Contest 77
这一题思路还是比较直接的,就是直接统计一下所有的前缀字符,然后看一下words当中各个前缀字符出现的频次,然后相加即可。
codename_cys
2022/05/07
2430
LeetCode 907. 子数组的最小值之和(单调栈)
给定一个整数数组 A,找到 min(B) 的总和,其中 B 的范围为 A 的每个(连续)子数组。
Michael阿明
2021/02/19
8060
LeetCode 1793. 好子数组的最大分数(单调栈)
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
Michael阿明
2021/09/06
4220
LeetCode 581. 最短无序连续子数组(排序&单调栈)
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
Michael阿明
2020/07/13
6100
LeetCode 581. 最短无序连续子数组(排序&单调栈)
子数组,你让我拿什么爱你?
周赛的时候被第二题卡了一下,自己之前做过子数组的问题,可以用单调栈优化,比赛的时候也往这方面想了
ACM算法日常
2021/12/20
3300
LeetCode 1856. 子数组最小乘积的最大值(前缀和 + 单调栈)
比方说,数组 [3,2,5] (最小值是 2)的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。 给你一个正整数数组 nums ,请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大,请你返回答案对 10^9 + 7 取余 的结果。
Michael阿明
2021/09/06
8120
凉经算法题反思 | 单调栈与DP二分法
这个过程引用到了单调栈的思想。就是一个栈,里面所有元素是非严格单调递增或者单调递减的。比较好思考,就是每一个数组都要越来越小,如果不满足递减的数字,说明要从栈中取出来几个数字了。
机器学习炼丹术
2020/08/04
7240
【面试高频题】难度 2/5,单调栈经典运用
对答案的贡献即是最终答案,但我们忽略了「当 nums 存在重复元素,且该元素作为子数组最大值时,最远左右端点的边界越过重复元素时,导致重复统计子数组」的问题。
宫水三叶的刷题日记
2023/10/25
3230
【面试高频题】难度 2/5,单调栈经典运用
LeetCode笔记:Weekly Contest 265
这题我算是取巧了,本身的难点在于链表的单向性,不过我这边先将其转换成了list,从而绕过了单向性问题,由此问题就变得简单了。
codename_cys
2021/11/02
3490
LeetCode 1630. 等差子数组
如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是 等差数列 。更正式地,数列 s 是等差数列,只需要满足:对于每个有效的 i , s[i+1] - s[i] == s[1] - s[0] 都成立。
Michael阿明
2021/02/19
3510
LeetCode 1063. 有效子数组的数目(单调栈)
文章目录 1. 题目 2. 解题 1. 题目 给定一个整数数组 A,返回满足下面条件的 非空、连续 子数组的数目: 子数组中,最左侧的元素不大于其他元素。 示例 1: 输入:[1,4,2,5,3] 输出:11 解释:有 11 个有效子数组,分别是:[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。 示例 2: 输入:[3,2,1] 输出:3 解释:有 3 个有效子数组,分别是:[3],[2],[1] 。 示例
Michael阿明
2021/02/19
7520
LeetCode笔记:Biweekly Contest 70
首先我们将价格进行排序,然后价格最大的两个必然只能靠自费,而后我们就可以免费获得价格第三高的糖果,重复上述操作即可可到最终的答案。
codename_cys
2022/04/13
4710
LeetCode 321. 拼接最大数(单调栈)*
给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。 现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
Michael阿明
2021/02/19
3020
LeetCode 992. K 个不同整数的子数组(双指针)
给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。
Michael阿明
2021/09/07
6850
Leetcode【75、153、795、945、1109】
颜色排序。给一个 012 数组,0、1、2 分别代表红色、白色和蓝色,将数组升序排序。要求只能遍历数组一次,并使用常量级的空间。
echobingo
2019/07/15
6240
JavaScript刷LeetCode拿offer-经典高频40题
工作太忙没有时间刷算法题,面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题,整理的内容有点长,建议先收藏,慢慢消化,在来年顺利拿到满意的offer。
hellocoder2028
2022/10/31
4730
推荐阅读
相关推荐
LeetCode笔记:Biweekly Contest 46 比赛记录
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验