本文涉及的基础知识点
LeetCode 3113. 边界元素是最大值的子数组数目
给你一个 正 整数数组 nums 。
请你求出 nums 中有多少个子数组,满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。
示例 1:
输入:nums = [1,4,3,3,2]
输出:6
解释:
总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值:
子数组 [1,4,3,3,2] ,最大元素为 1 ,第一个和最后一个元素都是 1 。
子数组 [1,4,3,3,2] ,最大元素为 4 ,第一个和最后一个元素都是 4 。
子数组 [1,4,3,3,2] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [1,4,3,3,2] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [1,4,3,3,2] ,最大元素为 2 ,第一个和最后一个元素都是 2 。
子数组 [1,4,3,3,2] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
所以我们返回 6 。
示例 2:
输入:nums = [3,3,3]
输出:6
解释:
总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值:
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
子数组 [3,3,3] ,最大元素为 3 ,第一个和最后一个元素都是 3 。
所以我们返回 6 。
示例 3:
输入:nums = [1]
输出:1
解释:
nums 中只有一个子数组 [1] ,最大元素为 1 ,第一个和最后一个元素都是 1 。
所以我们返回 1 。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
单调栈
枚举子数组的结尾nums[i],如果nums[j] < i,且j < i。那么它一定不是以nums[x]结尾的子数组的开始,故淘汰掉。x >= i。
淘汰后,栈中的数据降序。
淘汰后,我们统计和栈顶元素相等的数量。如果直接统计是:O(n),总用时就变成了O(nn)。
栈中的元素的格式如下:{num,cnt},num是值,cnt是和num相等的数量。
淘汰后,如果栈顶元素和当前元素相等,则cnt++;否则增加新元素{num,1}。
时间复杂度:O(n)
代码
class Solution { public: long long numberOfSubarrays(vector<int>& nums) { stack<pair<int, int>> staNumCnt; long long llRet = 0; for (const auto& n : nums) { while (staNumCnt.size() && (staNumCnt.top().first < n)) { staNumCnt.pop(); } if (staNumCnt.size() && (staNumCnt.top().first == n)) { staNumCnt.top().second++; } else { staNumCnt.emplace(n, 1); } llRet += staNumCnt.top().second; } return llRet; } };
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。