当前位置: 首页 > news >正文

力扣单调栈算法专题训练

目录

  • 1 专题说明
  • 2 训练

1 专题说明

本博客用来计算力扣上的单调栈题目、解题思路和代码。

单调栈题目记录:

  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 专题说明 本博客用来计算力扣上的单调栈题目、解题思路和代码。 单调栈题目记录&#xff1a; 2232866美丽塔II 2 训练 题目1&#xff1a;2866美丽塔II。 解题思路&#xff1a;先计算出prefix[i]&#xff0c;表示0~i满足递增情况下&#xff0c;0~i…...

【NI-RIO入门】理解Windows、Real Time与FPGA之间数据通信的原理

于NI kb摘录 1.概述 对于NI RIO系列设备&#xff08;CompactRIO、sbRIO、myRIO等&#xff09;进行编程时&#xff0c;需要注意有三个不同的组件。 人机界面 (HMI) 。有时称为“主机”&#xff0c;为用户提供图形用户界面&#xff08;GUI&#xff09;&#xff0c;用于监控系统…...

关于游戏性能优化的技巧

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

antdesignpro实现滚动加载分页数据

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

步兵 cocos2dx 加密和混淆

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

【算法设计与分析】——动态规划算法

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…...

WPF组合控件TreeView+DataGrid之DataGrid封装

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

PIL/Pillow

Abstract PIL(Python Imaging Library)是一个用于图像处理的 Python 库。它提供了广泛的功能&#xff0c;包括图像加载、保存、调整大小、裁剪、旋转、滤镜应用等。 由于 PIL 的开发停止在 2009 年&#xff0c;因此推荐使用其后续的维护版本 Pillow。Pillow 是一个兼容 PIL 接…...

ARM 汇编入门

ARM 汇编入门 引言 ARM 汇编语言是 ARM 架构的汇编语言&#xff0c;用于直接控制 ARM 处理器。虽然现代软件开发更多地依赖于高级语言和编译器&#xff0c;但理解 ARM 汇编仍然对于深入了解系统、优化代码和进行低级调试非常重要。本文将为您提供一个简单的 ARM 汇编入门指南…...

SQL进阶:多表查询

在SQL基础部分&#xff0c;我们在讲解的过程中只用到了单表查询。但实际上&#xff0c;常见的业务场景单表查询不能满足&#xff0c;或者拆分查询性能过慢。这个时候我们就需要用到连接查询。即查询多表按一定规则合并后的数据。 注意&#xff0c;合并后的数据也是表&#xff…...

多层负载均衡实现

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

Redis取最近10条记录

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

Mybatis之增删改查

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

Go 代码检查工具 golangci-lint

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

SwiftUI 趣谈之:绝不可能(Never)的 View!

概览 SwiftUI 的出现极大的解放了秃头码农们的生产力。SwiftUI 中众多原生和自定义视图对于我们创建精彩撩人的 App 功不可没&#xff01; 不过&#xff0c;倘若小伙伴们略微留意过 SwiftUI 框架头文件里的源代码&#xff0c;就会发现里面嵌有一些奇怪 Never 类型&#xff0c…...

etcd是什么

目录 1.关于etcd2.应用场景 本文主要介绍etcd 概念和基本应用场景。 1.关于etcd etcd是一个开源的、分布式的键值存储系统&#xff0c;用于共享配置和服务发现。它是由CoreOS团队开发的&#xff0c;主要用于实现分布式系统的配置管理和服务发现。 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数据库 触发器

目录 触发器概述 语法 案例 触发器概述 触发器是与表有关的数据库对象&#xff0c;指在insert/update/delete之前(BEFORE)或之后(AFTER)&#xff0c;触发并执行触发器中定义的soL语句集合。触发器的这种特性可以协助应用在数据库端确保数据的完整性&#xff0c;日志记录&am…...

C语言学习之给定任意的字符串,清除字符串中的空格

实例要求&#xff1a;给定任意的字符串&#xff0c;清除字符串中的空格&#xff0c;并将其输出&#xff1b;实例分析&#xff1a;1、指针函数实现&#xff0c;需要注意指针函数的返回值是一个指针类型&#xff1b;2、字符类型的数组实现&#xff0c;循环遍历并赋给新的数组&…...

由实验数据进行函数拟合的python实现

0.引言 已知公式求参的过程&#xff0c;对工程而言&#xff0c;一般是一个线性拟合或者非线性拟合的过程。我们现在来以代码片段为例&#xff0c;来描述如何求参。一般这个过程会涉及超定方程的计算。这个过程&#xff0c;原本需要使用matlab&#xff0c;现在python照样可以做…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;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. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...