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 的…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
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...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...