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

简介: 【单调栈】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 <= 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++**实现。

相关文章
|
2天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
11 3
|
2天前
数据结构初阶 栈
数据结构初阶 栈
7 1
|
7天前
|
存储
数据结构学习记录——堆的插入(堆的结构类型定义、最大堆的创建、堆的插入:堆的插入的三种情况、哨兵元素)
数据结构学习记录——堆的插入(堆的结构类型定义、最大堆的创建、堆的插入:堆的插入的三种情况、哨兵元素)
8 2
|
7天前
|
算法
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作(递归以及迭代实现-查找操作、查找最大和最小元素)
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作(递归以及迭代实现-查找操作、查找最大和最小元素)
8 0
|
7天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
11 0
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
14 2
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
13 0
|
16天前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
10天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
7天前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
9 0