【单调栈】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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。