leetcode316. 去除重复字母(单调栈 - java)
去除重复字母
- 题目描述
- 单调栈
- 代码演示
- 进阶优化
- 上期经典
题目描述
难度 - 中等
leetcode316. 去除重复字母
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = “bcabc”
输出:“abc”
示例 2:
输入:s = “cbacdcbc”
输出:“acdb”
提示:
1 <= s.length <= 1e4
s 由小写英文字母组成
单调栈
题目要求总共有三点:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。
根据要求三,我们就能想到这题可以用单调栈,用单调栈来保证字典序排列。
要求一,我们要去重,因此要加上出栈的条件。
只有在栈顶元素字典序靠后,且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈.
若输入为bcacc
- b 入栈
- c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
- a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.- c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
- c 入栈时栈中已经出现过c,跳过该元素
输出结果为 bac
代码演示
String removeDuplicateLetters(String s) {Stack<Character> sta = new Stack<>();//只有小写字母,所以可以用26长度就可以了int[] count = new int[26];//统计每个字出现的次数,方便判断何时可以出栈for (char c : s.toCharArray()){count[c - 'a']++;}boolean[] inStack = new boolean[26];for (char c : s.toCharArray()){//每遍历一个元素,就把字符出现的次数减一count[c - 'a']--;if (inStack[c - 'a']){continue;}//出栈的三个条件//栈内元素不为null//当前元素字典序小于之前入栈的元素//并且保证后面还有要弹出的元素,如果后面没有了,就不能弹出while(!sta.isEmpty() && sta.peek() > c && count[sta.peek() - 'a'] > 0){inStack[sta.pop() - 'a'] = false;}sta.push(c);inStack[c - 'a'] = true;}StringBuffer sb = new StringBuffer();while (!sta.isEmpty()){sb.append(sta.pop());}//栈先进后出,因此打印结果时要先逆序return sb.reverse().toString();}
进阶优化
上面解法中,我们用栈去保存元素,然后最后再倒进stringBuilder里,其实我们一开始就可以用StringBuilder,去存储元素,最后保留的结果,就是要的答案
代码演示:
String removeDuplicateLetters(String s) {Stack<Character> sta = new Stack<>();StringBuffer sb = new StringBuffer();char[] chars = s.toCharArray();int[] count = new int[256];for (int i = 0; i < chars.length;i++){count[chars[i] - 'a']++;}boolean[] inStack = new boolean[26];for (char c : chars){count[c - 'a']--;if (inStack[c - 'a']){continue;}while(sb.length() > 0 && sb.charAt(sb.length() - 1) > c && count[sb.charAt(sb.length() - 1) - 'a'] > 0){inStack[sb.charAt(sb.length() - 1) - 'a'] = false;sb.deleteCharAt(sb.length() - 1);}sb.append(c);inStack[c - 'a'] = true;}return sb.toString();}
上期经典
leetcode410. 分割数组的最大值
相关文章:

leetcode316. 去除重复字母(单调栈 - java)
去除重复字母 题目描述单调栈代码演示进阶优化 上期经典 题目描述 难度 - 中等 leetcode316. 去除重复字母 给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对…...
零散笔记:《Spring实战》Thymeleaf
1、Thymeleaf模板就是增加一些额外元素属性的HTML,这些属性能够指导模板如何渲染request数据。 <p th:test "${message}">placeholder message</p> th我推测是中文的”替换“。 2、th:each,迭代元素集合。 <div th:each &qu…...

WordArt Designer:基于用户驱动与大语言模型的艺术字生成
AIGC推荐 FaceChain人物写真开源项目,支持风格与穿着自定义,登顶github趋势榜首! 前言 本文介绍了一个基于用户驱动,依赖于大型语言模型(LLMs)的艺术字生成框架,WordArt Designer。 该系统包含四个关键模块:LLM引擎、…...

【C进阶】深度剖析数据在内存中的存储
目录 一、数据类型的介绍 1.类型的意义: 2.类型的基本分类 二、整形在内存中的存储 1.原码 反码 补码 2.大小端介绍 3.练习 三、浮点型在内存中的存储 1.一个例子 2.浮点数存储规则 一、数据类型的介绍 前面我们已经学习了基本的内置类型以及他们所占存储…...

TortoiseGit安装
一、安装Git环境 Git-2.42.0-64-bit.exe (访问密码: 1666)https://url48.ctfile.com/f/33868548-924037167-76e273?p1666 二、安装TortoiseGit TortoiseGit-2.14.0.1-64bit.msi (访问密码: 1666)https://url48.ctfile.com/f/33868548-924037173-d395c7?p1666 三、安装T…...

巨人互动|游戏出海游戏出海的趋势如何
随着全球游戏市场的不断扩大和消费者需求的多元化,游戏出海作为游戏行业的重要战略之一,正面临着新的发展趋势。本文小编将讲讲游戏出海的趋势,探讨一下未来游戏出海的发展方向与前景。 巨人互动|游戏出海&2023国内游戏厂商加快“出海”发…...

k8s 安装 istio(二)
3.3 部署服务网格调用链检测工具 Jaeger 部署 Jaeger 服务 kubectl apply -f https://raw.githubusercontent.com/istio/istio/release-1.16/samples/addons/jaeger.yaml 创建 jaeger-vs.yaml 文件 apiVersion: networking.istio.io/v1alpha3 kind: VirtualService metadata…...

Postman中参数区别及使用说明
一、Params与Body 二者区别在于请求参数在http协议中位置不一样。Params 它会将参数放入url中以?区分以&拼接Body则是将请求参数放在请求体中 后端接受数据: 二、body中不同格式 2.1 multipart/form-data key - value 格式输入,主要特点是可以上…...

基于python+pyqt的opencv汽车分割系统
目录 一、实现和完整UI视频效果展示 主界面: 识别结果界面: 查看分割处理过程图片界面: 二、原理介绍: 加权灰度化 编辑 二值化 滤波降噪处理 锐化处理 边缘特征提取 图像分割 完整演示视频: 完整代码链…...
游戏设计的主要部分
游戏设计的主要部分 介绍 游戏设计是创建有趣、挑战性和令人满足的游戏体验的过程。它涵盖了许多方面,从概念开发到实际实施,以及最终的游戏测试和优化。游戏设计师需要考虑玩家的情感、技能挑战、故事情节、游戏世界等多个要素,以确保游戏…...
架构师成长之路Redis第二篇|Redis配置文件参数讲解
Redis.conf文件 官网Redis文档链接:Redis官网 官网Redis config配置文件参数讲解:https://redis.io/docs/management/config/ Redis.conf参考模板例子 : https://redis.io/docs/management/config-file/ Redis 可以使用内置的默认配置在没有配置文件的情况下启动,但是仅…...

jsp+servlet+mysql阳光网吧管理系统
项目介绍: 本系统使用jspservletmysql开发的阳光网吧管理系统,纯手工敲打,系统管理员和用户角色,功能如下: 管理员:修改个人信息、修改密码;机房类型管理;机房管理;机位…...

Next.js基础语法
Next.js 目录结构 入口App组件(_app.tsx) _app.tsx是项目的入口组件,主要作用: 可以扩展自定义的布局(Layout)引入全局的样式文件引入Redux状态管理引入主题组件等等全局监听客户端路由的切换 ts.config…...
selenium进阶之web自动化项目框架搭建(Python版)
web自动化项目框架搭建 1、项目结构 web自动化框架的设计,同接口自动化框架一样,采用分层设计。 文件或目录说明common常用模块,常用的一些函数封装testcases用例模块,所有的测试用例test_data用例数据logs日志目录reports报告s…...

qt设计界面
widget.h #ifndef WIDGET_H #define WIDGET_H //防止文件重复包含#include <QWidget> //QWidget类所在的头文件,父类头文件 #include<QIcon> #include<QPushButton> …...

《C和指针》笔记12: 存储类型(自动变量、静态变量和寄存器变量)
文章目录 1. 自动变量(auto)1.1 自动变量的初始化 2. 静态变量(static)2.1 静态变量的初始化 3. 寄存器变量(register) 1. 自动变量(auto) 在代码块内部声明的变量的缺省存储类型是…...

无限计算力:探索云计算的无限可能性
这里写目录标题 前言云计算介绍服务模型: 应用领域:云计算主要体现在生活中的地方云计算未来发展的方向 前言 云计算是一种基于互联网的计算模型,通过它可以实现资源的共享、存储、管理和处理。它已经成为许多个人、企业和组织的重要技术基础…...

【赋权算法】Python实现熵权法
在开始之前,我们先说一下信息熵的概念。 当一件事情发生,如果是意料之中,那么这个事情就并不能拿来当做茶余饭后的谈资,我们可以说这个事情并没有什么信息和价值。而当一件不可能发生的事情发生的时候,我们可能就会觉…...

docker之 Consul(注册与发现)
目录 一、什么是服务注册与发现? 二、什么是consul 三、consul 部署 3.1建立Consul服务 3.1.1查看集群状态 3.1.2通过 http api 获取集群信息 3.2registrator服务器 3.2.1安装 Gliderlabs/Registrator 3.2.2测试服务发现功能是否正常 3.2.3验证 http 和 ng…...

用NeRFMeshing精确提取NeRF网络中的3D网格
准确的 3D 场景和对象重建对于机器人、摄影测量和 AR/VR 等各种应用至关重要。 NeRF 在合成新颖视图方面取得了成功,但在准确表示底层几何方面存在不足。 推荐:用 NSDT编辑器 快速搭建可编程3D场景 我们已经看到了最新的进展,例如 NVIDIA 的…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...

若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...