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

leetcode316. 去除重复字母(单调栈 - java)

去除重复字母

  • 题目描述
    • 单调栈
    • 代码演示
    • 进阶优化
  • 上期经典

题目描述

难度 - 中等
leetcode316. 去除重复字母

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:
输入:s = “bcabc”
输出:“abc”

示例 2:
输入:s = “cbacdcbc”
输出:“acdb”

提示:
1 <= s.length <= 1e4
s 由小写英文字母组成

在这里插入图片描述

单调栈

题目要求总共有三点:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。

根据要求三,我们就能想到这题可以用单调栈,用单调栈来保证字典序排列。
要求一,我们要去重,因此要加上出栈的条件。
只有在栈顶元素字典序靠后,且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈.

若输入为bcacc

  1. b 入栈
  2. c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
  3. a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
    元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
    元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.
  4. c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
  5. 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 &#xff0c;请你去除字符串中重复的字母&#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小&#xff08;要求不能打乱其他字符的相对…...

零散笔记:《Spring实战》Thymeleaf

1、Thymeleaf模板就是增加一些额外元素属性的HTML&#xff0c;这些属性能够指导模板如何渲染request数据。 <p th:test "${message}">placeholder message</p> th我推测是中文的”替换“。 2、th:each&#xff0c;迭代元素集合。 <div th:each &qu…...

WordArt Designer:基于用户驱动与大语言模型的艺术字生成

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

【C进阶】深度剖析数据在内存中的存储

目录 一、数据类型的介绍 1.类型的意义&#xff1a; 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…...

巨人互动|游戏出海游戏出海的趋势如何

随着全球游戏市场的不断扩大和消费者需求的多元化&#xff0c;游戏出海作为游戏行业的重要战略之一&#xff0c;正面临着新的发展趋势。本文小编将讲讲游戏出海的趋势&#xff0c;探讨一下未来游戏出海的发展方向与前景。 巨人互动|游戏出海&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中以&#xff1f;区分以&拼接Body则是将请求参数放在请求体中 后端接受数据: 二、body中不同格式 2.1 multipart/form-data key - value 格式输入&#xff0c;主要特点是可以上…...

基于python+pyqt的opencv汽车分割系统

目录 一、实现和完整UI视频效果展示 主界面&#xff1a; 识别结果界面&#xff1a; 查看分割处理过程图片界面&#xff1a; 二、原理介绍&#xff1a; 加权灰度化 ​编辑 二值化 滤波降噪处理 锐化处理 边缘特征提取 图像分割 完整演示视频&#xff1a; 完整代码链…...

游戏设计的主要部分

游戏设计的主要部分 介绍 游戏设计是创建有趣、挑战性和令人满足的游戏体验的过程。它涵盖了许多方面&#xff0c;从概念开发到实际实施&#xff0c;以及最终的游戏测试和优化。游戏设计师需要考虑玩家的情感、技能挑战、故事情节、游戏世界等多个要素&#xff0c;以确保游戏…...

架构师成长之路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阳光网吧管理系统

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

Next.js基础语法

Next.js 目录结构 入口App组件&#xff08;_app.tsx&#xff09; _app.tsx是项目的入口组件&#xff0c;主要作用&#xff1a; 可以扩展自定义的布局&#xff08;Layout&#xff09;引入全局的样式文件引入Redux状态管理引入主题组件等等全局监听客户端路由的切换 ts.config…...

selenium进阶之web自动化项目框架搭建(Python版)

web自动化项目框架搭建 1、项目结构 web自动化框架的设计&#xff0c;同接口自动化框架一样&#xff0c;采用分层设计。 文件或目录说明common常用模块&#xff0c;常用的一些函数封装testcases用例模块&#xff0c;所有的测试用例test_data用例数据logs日志目录reports报告s…...

qt设计界面

widget.h #ifndef WIDGET_H #define WIDGET_H //防止文件重复包含#include <QWidget> //QWidget类所在的头文件&#xff0c;父类头文件 #include<QIcon> #include<QPushButton> …...

《C和指针》笔记12: 存储类型(自动变量、静态变量和寄存器变量)

文章目录 1. 自动变量&#xff08;auto&#xff09;1.1 自动变量的初始化 2. 静态变量&#xff08;static&#xff09;2.1 静态变量的初始化 3. 寄存器变量&#xff08;register&#xff09; 1. 自动变量&#xff08;auto&#xff09; 在代码块内部声明的变量的缺省存储类型是…...

无限计算力:探索云计算的无限可能性

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

【赋权算法】Python实现熵权法

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

docker之 Consul(注册与发现)

目录 一、什么是服务注册与发现&#xff1f; 二、什么是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 在合成新颖视图方面取得了成功&#xff0c;但在准确表示底层几何方面存在不足。 推荐&#xff1a;用 NSDT编辑器 快速搭建可编程3D场景 我们已经看到了最新的进展&#xff0c;例如 NVIDIA 的…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

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; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* 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)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...