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

算法单调栈—Java版

单调栈

  • 概念:维护栈中元素的单调性,单调增或者单调减。

  • 什么时候用?

    • 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈的本质是空间换时间,在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素,优点是整个数组只需要遍历一次。因为我们遍历数组的时候,我们不知道之前都遍历了哪些元素,以至于遍历一个元素找不到是不是之前遍历过一个更小的,所以我们需要用一个容器(这里用单调栈)来记录我们遍历过的元素。
  • 如何用?

    • 当要求数组的每个元素的下一个最大元素时,维护单调递减栈,每次遇到栈顶元素<新进栈元素时,栈顶元素出栈,如果出栈了新的栈顶还是小于新进栈元素,则一直循环出栈进栈,新元素进栈,此时出栈的元素的右边第一个最大元素为新进栈元素。如果新进栈元素<栈顶元素时,则直接进栈。例如有数组 [3,5,1,4,8,3]的对应元素的下一个最大元素为[5,8,4,8,-1,-1],-1表示没有。维护单调递减栈 s=[] ,首先3进栈,s=[3],然后新进栈元素为5,比栈顶元素大,5进栈,3出栈,此时s=[5],即3右边第一个比它大的元素为5,然后是1比栈顶5小直接进栈,s=[5,1];然后遇见4,此时1出栈,4进栈,即第一个比1大的元素是4 ,s=[5,4]。

    • 总结:找第一个/下一个最大元素,维护递减栈;找第一个/下一个最小元素,维护递增栈。

LeetCode练习

import java.util.ArrayDeque;
public class Solution {public String removeDuplicateLetters(String s) {//使用单调栈保持字典序ArrayDeque<Character> stack = new ArrayDeque<Character>();int length = s.length();stack.addLast(s.charAt(0));StringBuffer res = new StringBuffer();for(int i=1;i<length;i++){int flag = 0;Character c = stack.getLast();String sub = s.substring(i,length);while (c>s.charAt(i) && !stack.contains(s.charAt(i)) && sub.contains(""+c) && !stack.isEmpty()){//栈顶元素大于待检测字符且栈中没有该元素,且栈顶元素后续还有 且栈非空 则出栈stack.pollLast();if(!stack.isEmpty())c = stack.getLast();flag = 1;}if(flag==1){// 出栈完成后,待检测字符入栈stack.addLast(s.charAt(i));}if(!stack.contains(s.charAt(i))){  //c<s.charAt(i) &&// 如果待检测字符小于c且栈中不包含它则直接进栈stack.addLast(s.charAt(i));}}while(!stack.isEmpty()){Character c = stack.pollLast();res.append(c);}return res.reverse().toString();}
}

相关文章:

算法单调栈—Java版

单调栈 概念&#xff1a;维护栈中元素的单调性&#xff0c;单调增或者单调减。 什么时候用&#xff1f; 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈的本质是空间换时间&#xff0c;在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元…...

在Linux中进行rocketmq及rocketmq控制台安装与配置

rocketmq下载安装的版本&#xff1a;rocketmq-rocketmq-all-5.0.0.tar.gz rocketmq控制台下载安装的版本&#xff1a;rocketmq-externals-rocketmq-console-1.0.0.tar.gz rocketmq安装 第一步&#xff0c;下载server-jre-8u202-linux-x64.tar.gz安装包。 登录网址&#xff…...

2023年全国最新食品安全管理员精选真题及答案4

百分百题库提供食品安全管理员考试试题、食品安全员考试预测题、食品安全管理员考试真题、食品安全员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 31.国家对食品添加剂生产实行____制度。 A.产品注册 B.产品备案 C.登…...

es-07脚本查询

脚本查询 概念 Scripting是Elasticsearch支持的一种专门用于复杂场景下支持自定义编程的强大的脚本功能&#xff0c;ES支持多种脚本语言&#xff0c;如painless&#xff0c;其语法类似于Java,也有注释、关键字、类型、变量、函数等&#xff0c;其就要相对于其他脚本高出几倍的性…...

JM员工福利与健康平台,企业关怀Always Online

庄信万丰(Johnson Matthey, JM)&#xff0c;全球性专用化学品公司&#xff0c;是可持续发展技术的全球领导者。在30多个国家和地区拥有13000多名员工。 JM的价值观之一是保护人类和地球。在生产过程中&#xff0c;JM保持对环境保护和能源清洁的高度关注&#xff1b;在员工福利…...

如何使用U-Mail搭建企业邮件服务器?

在当今的信息时代&#xff0c;企业也应该跟上时代的步伐。做好企业信息化建设&#xff0c;对企业事业单位尤为重要。电子邮件作为企业信息化过程中的重要组成部分&#xff0c;在企业内部沟通和外部沟通中发挥着重要作用。目前&#xff0c;有实力的企业已经开始倾向于自己搭建邮…...

用规则来搭建团队:写周报不一定是坏事

你好&#xff0c;我是Smile&#xff0c;一位有二十年工作经验的技术专家。今天我会结合我的经历&#xff0c;和你聊聊搭建技术团队这个话题。 众所周知&#xff0c;技术团队很大程度上决定了一个公司业务的生命力和生命周期&#xff0c;因此技术团队的投入成本往往很高&#x…...

Apollo使用方法

Apollo使用方法1.Apollo相关原理1.Apollo启动方法1.1 软件包方式1.2 脚本方式2.播放数据包2.1 软件包方式2.2 脚本方式3.试验planning模块4.从官网下载场景集其他工具1.Apollo相关原理 cyber / mainboard / mainboard.cc 是Apollo入口 cyber / mainboard / module_argument.cc…...

科研快讯 | 14篇论文被信号处理领域顶级国际会议ICASSP录用

ICASSP 2023 近日&#xff0c;2023年IEEE声学、语音与信号处理国际会议&#xff08;2023 IEEE International Conference on Acoustics, Speech, and Signal Processing&#xff0c;ICASSP 2023&#xff09;发布录用通知&#xff0c;清华大学人机语音交互实验室&#xff08;TH…...

设计模式—策略(Strategy)模式

一、概述策略模式的用意是针对一组算法&#xff0c;将每一个算法封装到具有共同接口的独立的类中&#xff0c;从而使得它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化使用策略模式可以把行为和环境分割开来。环境类负责维持和查询行为类&#xff0c;…...

STM32 触摸屏移植GUI控制控件

目录 1、emWin 支持指针输入设备。 2、 模拟触摸屏驱动 3、实现触摸屏的流程 3.1 实现硬件函数 3.2 实现对GUI_TOUCH_Exec()的定期调用 3.3 使用上一步确定的值&#xff0c;在初始化函数LCD_X_Config&#xff08;&#xff09;当中添加对GUI_TOUCH_Calibrate()的调用 4、…...

数仓模型之维度建模

目录 1、数仓架构原则 2、如何搭建一个好的数仓 2.1 建模方法 2.2 建模解决的痛点 2.3 数仓系统满足的特性 2.4 数仓架构设计 3、维度建模 4、案例 5、问题讨论 今天我们来聊聊在数仓模型中举足轻重的维度建模。 简单而言&#xff0c;数据仓库的核心目标是为展现层提…...

Servlet笔记(9):Cookie处理

一、Cookies处理 1、Cookies概念 Cookies是存储在客户端计算机上的文本文件&#xff0c;并保留各种跟踪信息。 识别返回用户的三个步骤 服务器脚本向浏览器发送一组Cookies。例如姓名、年龄或识别号码等。浏览器将这些信息存储在本地计算机上。当下一次浏览器向Web服务器发送…...

骨传导耳机是怎么传声的,选择骨传导耳机的时候需要注意什么?

​骨传导耳机之所以能够成为当下最火的耳机&#xff0c;骨传导技术将声音转化为震动感&#xff0c;通过骨头进行传播&#xff0c;不会堵塞耳朵&#xff0c;就不会影响到周围环境音。这种技术也让骨传导耳机比传统入耳式耳机更安全&#xff0c;无需入耳式设计&#xff0c;避免了…...

达梦数据库DSC集群部署

一、概述 1.1 DSC 集群架构 1.2 架构说明 1、DMDSC 集群是一个多实例、单数据库的系统。 多个数据库实例可以同时访问、修改同一个数据库的数据。 2、数据文件、控制文件在集群系统中只有一份,不论有几个节点,这些节点都平等地使用这些文件, 这些文件保存在共享存储上。 3…...

java 系列之Mybatis

java 系列文章 文章目录java 系列文章前言一、Mybatis 入门1.1 认识 框架&#xff08;了解&#xff09;1.2 认识 ORM&#xff08;要知道&#xff09;1.3 认识 Mybatis&#xff08;要知道&#xff09;二、Mybatis 使用2.1 创建maven项目并导入依赖2.2 准备数据库&#xff0c;包和…...

OBS 进阶 之 摄像头操作

目录 一、摄像头 1、win-dshow插件中,摄像头枚举操作 1)、视频源ID 2)、注册视频源信息...

Linux操作系统基础知识命令参数详解

Linux操作系统 RAID分组 RAID JBOD RAID JBOD的意思是Just a Bunch Of Disks&#xff0c;是将多块硬盘串联起来组成一个大的存储设备&#xff0c;从某种意义上说这种类型不被算作RAID&#xff0c;在维基百科里JBOD同时也被归入非RAID架构。RAID JBOD将所有的磁盘串联成一个单…...

Rust中一些K/V存储引擎

K/V存储引擎的由来可以追溯到20世纪70年代的Berkley DB&#xff0c;而近年来&#xff0c;随着互联网应用的发展&#xff0c;KV存储引擎因其简单高效、可扩展性和适合缓存应用等特点&#xff0c;在分布式存储领域得到了广泛应用。而使用Rust编写KV存储具有内存安全、高性能、并发…...

202302-第四周资讯

山川软件愿为您提供最优质的服务。 您的每一个疑问都会被认真对待&#xff0c;您的每一个建议都将都会仔细思考。 我们希望人人都能分析大数据&#xff0c;人人都能搭建应用。 因此我们将不断完善我们的DEMO、文档、以及视频&#xff0c;期望能在最大程度上快速帮助用户快速…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...

【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space

问题&#xff1a;IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案&#xff1a;将编译的堆内存增加一点 位置&#xff1a;设置setting-》构建菜单build-》编译器Complier...

云原生时代的系统设计:架构转型的战略支点

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、云原生的崛起&#xff1a;技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深&#xff0c;传统的 I…...