【单调栈】3113. 边界元素是最大值的子数组数目

本文涉及的基础知识点

单调栈分类、封装和总结

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 <= 10⁵
1 <= nums[i] <= 10⁹

单调栈

枚举子数组的结尾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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛