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

目录
打赏
0
0
0
0
36
分享
相关文章
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
54 1
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等