当前位置: 首页 > 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照样可以做…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...