力扣单调栈算法专题训练
目录
- 1 专题说明
- 2 训练
1 专题说明
本博客用来计算力扣上的单调栈题目、解题思路和代码。
单调栈题目记录:
- 2232866美丽塔II
2 训练
题目1:2866美丽塔II。
解题思路:先计算出prefix[i],表示0~i
满足递增情况下,0~i
上的元素之和最大值。然后计算出suffix[i],表示i~n-1
满足递增情况下,i~n-1
上的元素之和最大值。那么以i
为峰顶的美丽塔的元素之和的最大值为prefix[i] + suffix[i] - nums[i]
,遍历i,获得答案即可。
本质上,还是可以归类为:找到i左边,并且<=nums[i]的元素值。
C++代码如下,
class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {int n = maxHeights.size();vector<long long> prefix(n, 0); //prefix[i]表示0~i是递增的情况下,0~i的元素之和stack<int> stk;for (int i = 0; i < n; ++i) {while (!stk.empty() && maxHeights[stk.top()] > maxHeights[i]) {stk.pop();}if (stk.empty()) {prefix[i] = (long long)(i + 1) * maxHeights[i];} else {prefix[i] = prefix[stk.top()] + (long long)(i - stk.top()) * maxHeights[i];}stk.push(i);}while (!stk.empty()) {stk.pop();}vector<long long> suffix(n, 0); //suffix[i]表示i~n-1是递减的情况下,i~n-1的元素之和for (int i = n - 1; i >= 0; --i) {while (!stk.empty() && maxHeights[stk.top()] > maxHeights[i]) {stk.pop();}if (stk.empty()) {suffix[i] = (long long)(n - i) * maxHeights[i];} else {suffix[i] = suffix[stk.top()] + (long long)(stk.top() - i) * maxHeights[i];}stk.push(i);}long long res = 0;for (int i = 0; i < n; ++i) {res = max(res, prefix[i] + suffix[i] - maxHeights[i]);}return res;}
};
python3代码如下,
class Solution:def maximumSumOfHeights(self, maxHeights: List[int]) -> int:n = len(maxHeights)prefix = [0 for i in range(n)] #0~i的递增数组的和的最大值stk = []for i in range(n):while len(stk) and maxHeights[stk[-1]] > maxHeights[i]:del stk[-1]if len(stk) == 0:prefix[i] = (i + 1) * maxHeights[i]else:prefix[i] = prefix[stk[-1]] + (i - stk[-1]) * maxHeights[i]stk.append(i)stk.clear()suffix = [0 for i in range(n)] #i~n-1的递减数组的和的最大值for i in range(n-1,-1,-1):while len(stk) and maxHeights[stk[-1]] > maxHeights[i]:del stk[-1]if len(stk) == 0:suffix[i] = (n - i) * maxHeights[i]else:suffix[i] = suffix[stk[-1]] + (stk[-1] - i) * maxHeights[i]stk.append(i)res = 0for i in range(n):#print(f"i = {i}, prefix[i] = {prefix[i]}, suffix[i] = {suffix[i]}.")res = max(res, prefix[i] + suffix[i] - maxHeights[i])return res
题目2:496下一个更大元素I。
解题思路:直接找右边首次大于它的元素即可。
C++代码如下,
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> mp; //mp[x]表示nums2中元素x的右边,第一个比它大的元素stack<int> stk;for (int i = nums2.size() - 1; i >= 0; --i) {while (!stk.empty() && stk.top() <= nums2[i]) {stk.pop();}if (!stk.empty()) {mp[nums2[i]] = stk.top();} else {mp[nums2[i]] = -1;}stk.push(nums2[i]);}vector<int> res;for (auto x : nums1) {res.emplace_back(mp[x]);}return res;}
};
python3代码如下,
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:n = len(nums2)mp = collections.defaultdict(int)stk = []for i in range(n - 1, -1, -1):while len(stk) and stk[-1] <= nums2[i]:del stk[-1]if len(stk):mp[nums2[i]] = stk[-1]else:mp[nums2[i]] = -1stk.append(nums2[i])res = []for x in nums1:res.append(mp[x])return res
题目3:503下一个更大元素II。
解题思路:环形问题,扩展两倍原数组即可,接下来就是找右侧首次大于它的元素。
C++代码如下,
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int> a(2 * n, 0);for (int i = 0; i < n; ++i) {a[i] = a[i + n] = nums[i];}vector<int> ans(2 * n, -1);stack<int> stk;for (int i = 2 * n - 1; i >= 0; --i) {while (!stk.empty() && stk.top() <= a[i]) {stk.pop();}if (!stk.empty()) {ans[i] = stk.top();}stk.push(a[i]);}vector<int> res(n, -1);for (int i = 0; i < n; ++i) {res[i] = ans[i];}return res;}
};
python3代码如下,
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)a = [-1 for i in range(2 * n)]for i in range(n):a[i] = a[i + n] = nums[i]ans = [-1 for i in range(2 * n)]stk = []for i in range(2 * n - 1, -1, -1):while len(stk) and stk[-1] <= a[i]:del stk[-1]if len(stk):ans[i] = stk[-1]stk.append(a[i])res = [-1 for i in range(n)]for i in range(n):res[i] = ans[i]return res
题目4:2454下一个更大元素IV。
解题思路:比较难,不懂先放一边。
题目5:
相关文章:

力扣单调栈算法专题训练
目录 1 专题说明2 训练 1 专题说明 本博客用来计算力扣上的单调栈题目、解题思路和代码。 单调栈题目记录: 2232866美丽塔II 2 训练 题目1:2866美丽塔II。 解题思路:先计算出prefix[i],表示0~i满足递增情况下,0~i…...

【NI-RIO入门】理解Windows、Real Time与FPGA之间数据通信的原理
于NI kb摘录 1.概述 对于NI RIO系列设备(CompactRIO、sbRIO、myRIO等)进行编程时,需要注意有三个不同的组件。 人机界面 (HMI) 。有时称为“主机”,为用户提供图形用户界面(GUI),用于监控系统…...

关于游戏性能优化的技巧
关于游戏性能优化的技巧 游戏性能优化对象池Jobs、Burst、多线程间隔处理定时更新全局广播缓存组件缓存常用数据2D残影优化2D骨骼转GPU动画定时器优化DrawCall合批处理优化碰撞层优化粒子特效 游戏性能优化 好久没有在CSDN上面写文章了,今天突然看到鬼谷工作室技术…...

antdesignpro实现滚动加载分页数据
原理解析:每滚动一次相当于翻页,请求后端时给的页码参数要想办法加1,后端才能根据页码给出相应数据 注意后端收到页码参数之后要准确计算出每页的首行数据,关键逻辑代码: # 根据前端传的页码,进行计算下一…...

步兵 cocos2dx 加密和混淆
文章目录 摘要引言正文代码加密具体步骤代码加密具体步骤测试和配置阶段IPA 重签名操作步骤 总结参考资料 摘要 本篇博客介绍了针对 iOS 应用中的 Lua 代码进行加密和混淆的相关技术。通过对 Lua 代码进行加密处理,可以确保应用代码的安全性,同时提高性…...

【算法设计与分析】——动态规划算法
🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:…...

WPF组合控件TreeView+DataGrid之DataGrid封装
(关注博主后,在“粉丝专栏”,可免费阅读此文) wpf的功能非常强大,很多控件都是原生的,但是要使用TreeViewDataGrid的组合,就需要我们自己去封装实现。 我们需要的效果如图所示&#x…...

PIL/Pillow
Abstract PIL(Python Imaging Library)是一个用于图像处理的 Python 库。它提供了广泛的功能,包括图像加载、保存、调整大小、裁剪、旋转、滤镜应用等。 由于 PIL 的开发停止在 2009 年,因此推荐使用其后续的维护版本 Pillow。Pillow 是一个兼容 PIL 接…...
ARM 汇编入门
ARM 汇编入门 引言 ARM 汇编语言是 ARM 架构的汇编语言,用于直接控制 ARM 处理器。虽然现代软件开发更多地依赖于高级语言和编译器,但理解 ARM 汇编仍然对于深入了解系统、优化代码和进行低级调试非常重要。本文将为您提供一个简单的 ARM 汇编入门指南…...
SQL进阶:多表查询
在SQL基础部分,我们在讲解的过程中只用到了单表查询。但实际上,常见的业务场景单表查询不能满足,或者拆分查询性能过慢。这个时候我们就需要用到连接查询。即查询多表按一定规则合并后的数据。 注意,合并后的数据也是表ÿ…...

多层负载均衡实现
1、单节点负载均衡 1)站点层与浏览器层之间加入了一个反向代理层,利用高性能的nginx来做反向代理 2)nginx将http请求分发给后端多个web-server 优点: 1)DNS-server不需要动 2)负载均衡:通过ngi…...

Redis取最近10条记录
有时候我们有这样的需求,就是取最近10条数据展示,这些数据不需要存数据库,只用于暂时最近的10条,就没必要在用到Mysql类似的数据库,只需要用redis即可,这样既方便也快! 具体取最近10条的方法&a…...

Mybatis之增删改查
目录 一、引言 二、Mybatis——增 举例:添加用户 三、Mybatis——删 举例:删除用户 四、Mybatis——改 举例:修改用户 五、Mybatis——查 六、注意 END: 一、引言 书接上回,我们在了解完mybatis之后,肯…...

Go 代码检查工具 golangci-lint
一、介绍 golangci-lint 是一个代码检查工具的集合,聚集了多种 Go 代码检查工具,如 golint、go vet 等。 优点: 运行速度快可以集成到 vscode、goland 等开发工具中包含了非常多种代码检查器可以集成到 CI 中这是包含的代码检查器列表&…...

SwiftUI 趣谈之:绝不可能(Never)的 View!
概览 SwiftUI 的出现极大的解放了秃头码农们的生产力。SwiftUI 中众多原生和自定义视图对于我们创建精彩撩人的 App 功不可没! 不过,倘若小伙伴们略微留意过 SwiftUI 框架头文件里的源代码,就会发现里面嵌有一些奇怪 Never 类型,…...
etcd是什么
目录 1.关于etcd2.应用场景 本文主要介绍etcd 概念和基本应用场景。 1.关于etcd etcd是一个开源的、分布式的键值存储系统,用于共享配置和服务发现。它是由CoreOS团队开发的,主要用于实现分布式系统的配置管理和服务发现。 etcd的主要特性包括&#x…...

应用全局的UI状态存储AppStorage
目录 1、概述 2、StorageProp 2.1、观察变化和行为表现 3、StorageLink 3.1、观察变化和行为表现 4、从应用逻辑使用AppStorage和LocalStorage 5、从UI内部使用AppStorage和LocalStorage 6、不建议借助StorageLink的双向同步机制实现事件通知 6.1、推荐的事件通知方式…...

MySQL数据库 触发器
目录 触发器概述 语法 案例 触发器概述 触发器是与表有关的数据库对象,指在insert/update/delete之前(BEFORE)或之后(AFTER),触发并执行触发器中定义的soL语句集合。触发器的这种特性可以协助应用在数据库端确保数据的完整性,日志记录&am…...
C语言学习之给定任意的字符串,清除字符串中的空格
实例要求:给定任意的字符串,清除字符串中的空格,并将其输出;实例分析:1、指针函数实现,需要注意指针函数的返回值是一个指针类型;2、字符类型的数组实现,循环遍历并赋给新的数组&…...
由实验数据进行函数拟合的python实现
0.引言 已知公式求参的过程,对工程而言,一般是一个线性拟合或者非线性拟合的过程。我们现在来以代码片段为例,来描述如何求参。一般这个过程会涉及超定方程的计算。这个过程,原本需要使用matlab,现在python照样可以做…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...