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

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Java入门学习详细版(一)

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

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...