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

【算法】单调栈题单——字典序最小⭐(一种类型的模板题)

文章目录

  • 题目列表
    • 316. 去除重复字母⭐⭐⭐⭐⭐(类型题模板:单调栈,字典序最小)
    • 221021天池-03. 整理书架(保留数量为 limit 的字典序最小)
    • 402. 移掉 K 位数字(最多删除 k 次 + 前导零的处理)
    • 321. 拼接最大数🚹🚹🚹🚹🚹(繁琐)(分成两组+合并)💩
  • 相关链接

题目列表

从第一题模板题入手。

316. 去除重复字母⭐⭐⭐⭐⭐(类型题模板:单调栈,字典序最小)

https://leetcode.cn/problems/remove-duplicate-letters/description/

在这里插入图片描述
注意:该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同

冷静分析,先去掉一个字符,该去掉哪一个? 为了字典序越小,肯定要越往前的字符越小越好,那么就应该将最靠前的,且满足s[i]>s[i+1]的那个s[i]删掉即可。

怎么模拟多次这个过程呢?由于最先被删掉的一定更靠前,所以可以使用单调栈从前到后维护保留下来的字符。

除此之外,

  1. 要求每种原来就有的字符至少会保留下来一次,因此如果之后没有这种字符了,那么就不应该将其pop出栈。
  2. 如果一个字符已经在栈中了,那么后续的字符就不需要再加入栈了。

可以直接使用StringBuilder作为栈。

class Solution {public String removeDuplicateLetters(String s) {int[] cnt = new int[128];for (char ch: s.toCharArray()) cnt[ch]++;   // 记录各个字符剩余的数量StringBuilder ans = new StringBuilder();    // StringBuilder可以当栈使用for (char ch: s.toCharArray()) {cnt[ch]--;                              // 将剩余数量-1if (ans.indexOf(String.valueOf(ch)) != -1) continue;         // 如果前面已经有ch了,后面不需要再有了// 将stk中比当前ch更大且后面还有剩余的字符pop出去while (ans.length() > 0 && ch <= ans.charAt(ans.length() - 1) && cnt[ans.charAt(ans.length() - 1)] > 0) {ans.deleteCharAt(ans.length() - 1);}ans.append(ch);}return ans.toString();}
}

也可以使用栈,再转换成字符串。

class Solution {public String removeDuplicateLetters(String s) {int[] cnt = new int[128];for (char ch: s.toCharArray()) cnt[ch]++;   // 记录各个字符剩余的数量Deque<Character> stk = new ArrayDeque<>();for (char ch: s.toCharArray()) {cnt[ch]--;                              // 将剩余数量-1if (stk.contains(ch)) continue;         // 如果前面已经有ch了,后面不需要再有了// 将stk中比当前ch更大且后面还有剩余的字符pop出去while (!stk.isEmpty() && ch <= stk.peek() && cnt[stk.peek()] > 0) {stk.pop();}stk.push(ch);}// 将栈中的结果转成String返回StringBuilder ans = new StringBuilder();while (!stk.isEmpty()) ans.append(stk.pop());return ans.reverse().toString();}
}

221021天池-03. 整理书架(保留数量为 limit 的字典序最小)

https://leetcode.cn/contest/tianchi2022/problems/ev2bru/

在这里插入图片描述
提示:

1 <= order.length <= 10^5
1 <= limit <= 10
1 <= order[i] <= 10^6

class Solution {public int[] arrangeBookshelf(int[] order, int limit) {Deque<Integer> stk = new ArrayDeque<>();// 分别记录剩余的数量,在栈中的数量Map<Integer, Integer> cnt_residue = new HashMap<>(), cnt2 = new HashMap<>();for (int x: order) cnt_residue.merge(x, 1, Integer::sum);for (int x: order) {cnt_residue.merge(x, -1, Integer::sum);if (cnt2.getOrDefault(x, 0) >= limit) continue;     // 如果栈中已经有足够的x了,就不再添加进去// 要求栈中的元素+剩余的元素>limit才会被弹出while (!stk.isEmpty() && x < stk.peek() && cnt_residue.get(stk.peek()) + cnt2.getOrDefault(stk.peek(), 0) > limit) {cnt2.merge(stk.peek(), -1, Integer::sum);stk.pop();}stk.push(x);cnt2.merge(x, 1, Integer::sum);}int n = stk.size();int[] ans = new int[n];for (int i = n - 1; i >= 0; --i) {ans[i] = stk.pop();}return ans;}
} 

402. 移掉 K 位数字(最多删除 k 次 + 前导零的处理)

https://leetcode.cn/problems/remove-k-digits/description/

在这里插入图片描述

跟之前题目的区别在于,最多删除k次。
以及0可以不删,留着当前导零直接去除。

class Solution {public String removeKdigits(String num, int k) {Deque<Character> stk = new ArrayDeque<>();for (char x: num.toCharArray()) {while (!stk.isEmpty() && x < stk.peek() && k > 0) {stk.pop();k--;}stk.push(x);}// 如果还有没用的k,从后往前删除while (!stk.isEmpty() && k-- > 0) stk.pop();if (stk.size() == 0) return "0";    StringBuilder ans = new StringBuilder();while (!stk.isEmpty()) ans.append(stk.pop());// 去除前导零while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') ans.deleteCharAt(ans.length() - 1);return ans.reverse().toString();}
}

321. 拼接最大数🚹🚹🚹🚹🚹(繁琐)(分成两组+合并)💩

https://leetcode.cn/problems/create-maximum-number/description/

在这里插入图片描述

class Solution {public int[] maxNumber(int[] nums1, int[] nums2, int k) {int m = nums1.length, n = nums2.length;int[] maxSubSequence = new int[k];int start = Math.max(0, k - n), end = Math.min(k, m);for (int i = start; i <= end; ++i) {int[] subSequence1 = maxSubSequence(nums1, i);int[] subSequence2 = maxSubSequence(nums2, k - i);int[] curMaxSubSequence = merge(subSequence1, subSequence2);if (compare(curMaxSubSequence, 0, maxSubSequence, 0) > 0) {System.arraycopy(curMaxSubSequence, 0, maxSubSequence, 0, k);}}return maxSubSequence;}// 求最大子序列public int[] maxSubSequence(int[] nums, int k) {int n = nums.length;int[] stk = new int[k];int top = -1, remain = n - k;for (int i = 0; i < n; ++i) {int num = nums[i];while (top >= 0 && num > stk[top] && remain > 0) {top--;remain--;}if (top < k - 1) {stk[++top] = num;} else {--remain;}}return stk;}// 合并两个子序列public int[] merge(int[] subSequence1, int[] subSequence2) {int x = subSequence1.length, y = subSequence2.length;if (x == 0) return subSequence2;if (y == 0) return subSequence1;int mergeLength = x + y;int[] res = new int[mergeLength];int index1 = 0, index2 = 0;for (int i = 0; i < mergeLength; ++i) {if (compare(subSequence1, index1, subSequence2, index2) > 0) {res[i] = subSequence1[index1++];} else {res[i] = subSequence2[index2++];}}return res;}// 比较两个子序列的大小public int compare(int[] subSequence1, int index1, int[] subSequence2, int index2) {int x = subSequence1.length, y = subSequence2.length;while (index1 < x && index2 < y) {int diff = subSequence1[index1] - subSequence2[index2];if (diff != 0) return diff;index1++;index2++;}return (x - index1) - (y - index2);}
}

相关链接

【算法】单调栈题单(矩阵系列、字典序最小、贡献法)

相关文章:

【算法】单调栈题单——字典序最小⭐(一种类型的模板题)

文章目录 题目列表316. 去除重复字母⭐⭐⭐⭐⭐&#xff08;类型题模板&#xff1a;单调栈&#xff0c;字典序最小&#xff09;221021天池-03. 整理书架&#xff08;保留数量为 limit 的字典序最小&#xff09;402. 移掉 K 位数字&#xff08;最多删除 k 次 前导零的处理&…...

DockerCompose修改某个服务的配置(添加或编辑端口号映射)后如何重启单个服务使其生效

场景 docker-compose入门以及部署SpringBootVueRedisMysql(前后端分离项目)以若依前后端分离版为例&#xff1a; docker-compose入门以及部署SpringBootVueRedisMysql(前后端分离项目)以若依前后端分离版为例_docker-compose部署java mysql redis-CSDN博客 上面讲了docker c…...

DOM 事件的传播机制

前端面试大全DOM 事件的传播机制 &#x1f31f;经典真题 &#x1f31f;事件与事件流 事件流 事件冒泡流 事件捕获流 标准 DOM 事件流 &#x1f31f;事件委托 &#x1f31f;真题解答 &#x1f31f;总结 &#x1f31f;经典真题 谈一谈事件委托以及冒泡原理 &#x1f3…...

(数据结构)顺序表的查找

静态分配代码&#xff1a; #include<stdio.h> #include<stdlib.h> #define MAX 100 typedef struct LinkList {int data[MAX];int lenth; }Link; //初始化 void CreateList(Link* L) {L->lenth 0;for (int i 0; i < MAX; i){L->data[i] 0;} } //插入 …...

vue 解决响应大数据表格渲染崩溃问题

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; 1.场景描述 发起请求获取上万条数据&#xff0c;进行表格渲染&#xff0c;使浏览器卡顿&#xff0c;导致网页崩溃。 2.分析原因 1.大量数据加载&#xff0c;过多操作Dom&#xff0c;消耗性能。 2.表格中包含其他…...

Hdoop学习笔记(HDP)-Part.13 安装Ranger

目录 Part.01 关于HDP Part.02 核心组件原理 Part.03 资源规划 Part.04 基础环境配置 Part.05 Yum源配置 Part.06 安装OracleJDK Part.07 安装MySQL Part.08 部署Ambari集群 Part.09 安装OpenLDAP Part.10 创建集群 Part.11 安装Kerberos Part.12 安装HDFS Part.13 安装Ranger …...

Spring AOP记录接口访问日志

Spring AOP记录接口访问日志 介绍应用范围组成通知&#xff08;Advice&#xff09;连接点&#xff08;JoinPoint&#xff09;切点&#xff08;Pointcut&#xff09;切面&#xff08;Aspect&#xff09;引入&#xff08;Introduction&#xff09;织入&#xff08;Weaving&#x…...

分享89个节日PPT,总有一款适合您

分享89个节日PPT&#xff0c;总有一款适合您 89个节日PPT下载链接&#xff1a;https://pan.baidu.com/s/1j6Yj-7UCcUyV4V_S_eGjpQ?pwd6666 提取码&#xff1a;6666 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整理更不易…...

PostgreSQL日志中的SQL记录时机 —— log_statement 和 log_min_duration_statement

最近跟朋友讨论到PostgreSQL日志中的SQL记录时机&#xff0c;研究了下log_statement 和 log_min_duration_statement两个参数&#xff0c;记录一下。 一、 参数简介 1. log_statement ① 作用 控制记录SQL的类型&#xff0c;可选值为&#xff1a; none&#xff1a;关闭&…...

Agent举例与应用

什么是Agent OpenAI 应用研究主管 Lilian Weng 在一篇长文中提出了 Agent LLM&#xff08;大型语言模型&#xff09;记忆规划技能工具使用这一概念&#xff0c;并详细解释了Agent的每个模块的功能。她对Agent未来的应用前景充满信心&#xff0c;但也表明到挑战无处不在。 现…...

CentOS 7 配置tomcat

简介 Tomcat是一个使用Java编写的开源Web应用服务器,是由Apache Software Foundation管理的一个项目。它是一个轻量级的应用服务器,可以下载、安装和使用,而且还提供了许多高级功能,例如支持Java Servlet、JavaServer Pages (JSP)和JavaServer Faces (JSF) 等JavaEE技术,…...

如何优雅的关闭一个IIS站点

众所周知&#xff0c;当我们使用IIS的时候&#xff0c;在使用负载均衡的情况下&#xff0c;想停掉一个站点&#xff0c;通常会点击Sites&#xff08;网站&#xff09;中的Stop&#xff08;停止&#xff09;来停止一个站点。但是这样做&#xff0c;会带来一个问题&#xff0c;当…...

弱网模拟工具

一、背景 一个人晚上在家通过 Wi-Fi 上网&#xff0c;在线电影播放基本流畅&#xff0c;可一旦在晚间用网高峰期打视频电话就画面糊&#xff0c;这时不仅可能带宽受限了&#xff0c;还可能有较高的丢包率。与有线网络通信相比&#xff0c;无线网络通信受环境影响会更大&#x…...

Leetcode 第 110 场双周赛 Problem D 2809. 使数组和小于等于 x 的最少时间(DP+贪心+正难则反)

Leetcode 第 110 场双周赛 Problem D 2809. 使数组和小于等于 x 的最少时间&#xff08;DP 好题&#xff09;题目 给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒&#xff0c;对于所有下标 0 < i < nums1.length &#xff0c;nums1[i] 的值都增加 num…...

已知数组A[1..n]中元素类型为非负整数,设计算法将其调整为左右两部分,左边所有为奇数,右边所有为偶数,并要求算法的时间复杂度为O(n)

//左边奇数右边偶数 void Swap(int* a, int* b) {int tmp *b;*b *a;*a tmp; } void LeftRight(int arr[],int n) {int i 0;int j n - 1;while(i<j){if (arr[i] % 2 0 && arr[j] % 2 1) {Swap(&arr[i], &arr[j]);i;j--;}else if (arr[i] % 2 1 &…...

ssm+vue的罪犯信息管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频&#xff1a; ssmvue的罪犯信息管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;ssm vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…...

Java/Android 各类型数据构造和各类型数据解析

Java/Android 各类型数据构造和各类型数据解析 1.如何构造/解析{"key":"value","key":"value","key":"value"}jsonString1)json解析2)fastjson解析3)Gson解析4)遍历key值解析2.如何构造/解析[{"key&q…...

Linux系统---环境变量+内核进程调度队列(选学)

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、环境变量 1.基本概念 环境变量(environment variables)一般是指在操作系统中用来指定操作系统运行环境的一些参数&#xff0c…...

Kubernetes 使用插件扩展 kubectl

例子演示 编写 kubectl-foo &#xff0c;拷贝至 /usr/local/bin/ #!/bin/bash# 可选的参数处理 if [[ "$1" "version" ]] thenecho "1.0.0"exit 0 fi# 可选的参数处理 if [[ "$1" "config" ]] thenecho $KUBECONFIGexit…...

前端面试题09

74、定义类的方法有哪些 在JavaScript中&#xff0c;定义类的方法有以下几种方式&#xff1a; 1.使用函数声明&#xff1a; function MyClass() {// constructor } MyClass.prototype.methodName function() {// method body };2.使用类的方法缩写&#xff08;ES6引入&…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...