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

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
28 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
初步认识栈和队列
初步认识栈和队列
58 10
|
30天前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
43 3