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

【LeetCode每日一题】单调栈 402 移掉k位数字

402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k **位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 :

输入:num = "1432219", k = 3
输出:"1219"
解释:移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

如果有 m+1 位数字,S1

a 0 a 1 a 2 . . . . a m a_0a_1a_2....a_m a0a1a2....am

需要去掉n位数字,S2

a i , a k , , , , a n a_i,a_k,,,,a_n ai,ak,,,,an

剩余的 m+1-n 位。S3

假如用去掉的 n 位数字中的一个数字

a i ( a i < a j ) a_i (a_i < a_j) aiai<aj

替换剩余的 S3 里面的最大的字符 (a_j), 那么 新的数字会比原来的S3 要小,因此,我们用来去掉的n位数字中的每一个数字都需要大于剩余的数字

⇒ 去掉前N个最大的数字。

⇒ 通过单调栈去掉极大值,尖峰。

经过上面的分析,我们基本可以确定需要使用栈来充当这个容器了。当遍历每一个数字的时候,如果当前数字比栈顶数字大,是递增,那么就可以直接入栈,因为下一个数字有可能比当前的大;如果当前数字比栈顶的小,那么就需要将栈顶的元素弹出删除,因为这个栈顶元素既是递增的最后一个数字,也是递减的第一个数字,是一个尖峰,再删除过程中记录删除的个数或者将k - 1,当删除了所有k个数字后,就得出了结果。

遍历完毕后,k个数字没有移除完,比如数字123456789,移除3个数字,按照上面的分析,得出的结果还是123456789,出现这种情况是因为移除部分数字后,得出的结果是一个高位递增的数,所以无法再移除了,这个时候,只要出现这种情况,将低位的数字移除掉剩余个数即可,可以仔细想想这一个特殊点

var removeKdigits = function(num, k) {if(k === num.length){return "0";}let stack = [];for(let i = 0; i < num.length; i++){// 遇到尖峰,去掉尖峰  || 单调递减while(k && stack.length && stack.at(-1) > num[i]){stack.pop();k--;}// 维护的是一个递增的栈,但是首位不能是0if(!(nums[i]==="0" && stack.length === 0)){stack.push(num[i]);}}// 移除尖峰,如果没有尖峰,就把低位的删除即可 ||单调递增while(k>0 && stack.length){stack.pop();k--;}return stack.length === 0 ? "0" : stack.join("");};

相关文章:

【LeetCode每日一题】单调栈 402 移掉k位数字

402. 移掉 K 位数字 给你一个以字符串表示的非负整数 num 和一个整数 k &#xff0c;移除这个数中的 k **位数字&#xff0c;使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 &#xff1a; 输入&#xff1a;num "1432219", k 3 输出&#xff…...

力扣 309. 买卖股票的最佳时机含冷冻期

题目来源&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/ C题解&#xff1a;动态规划 状态1&#xff1a;表示持有股票。更新为之前持有股票&#xff08;dp[i-1][0]&#xff09;或者不持有股票且不处于冷冻期后买入&…...

2024年刷题记录

马上要开始找实习了&#xff0c;又开始重启刷题计划了&#xff01;加油冲冲冲&#xff01;刷题的顺序follow代码随想录的60天刷题计划&#xff01;感谢FuCosmo的总结&#xff01;之前都是按照C的语法进行刷题的&#xff0c;这次也同样使用C。 Day 1 数组 这些题过年前都刷过了…...

【JGit 】简述及学习资料整理

JGit 介绍 [官网](JGit | The Eclipse Foundation): https://www.eclipse.org/jgit/ 用户指南 : https://github.com/eclipse-jgit/jgit/wiki/User-Guide JGit是一个用于Java编程语言的开源Git实现。它提供了一组Java库和API&#xff0c;使开发人员可以在他们的Java应用程序…...

python数据类型-集合set

1 集合&#xff08;set&#xff09;的定义 1.1 集合是一个无序且不重复元素的序列&#xff1a; 1&#xff09;无序&#xff1a;存储顺序和添加的顺序不一定相同&#xff0c;不支持索引、切片 2&#xff09;元素不重复&#xff1a;当添加重复元素时&#xff0c;集合会自动去重…...

excel如何指定求和

在Excel中&#xff0c;你可以使用函数来实现动态求和&#xff0c;使得当指定行的数值更新后&#xff0c;和也随之更新。具体来说&#xff0c;你可以使用SUM函数结合一些动态的引用方法。以下是一种实现方式&#xff1a; 假设你要对A列&#xff08;从A1到A10&#xff0c;以示例…...

服务端实时推送技术之SSE(Server-Send Events)

文章目录 前言一、解决方案&#xff1a;1、传统实时处理方案&#xff1a;2、HTML5 标准引入的实时处理方案&#xff1a;3、第三方推送&#xff1a; 二、SSE1.引入库1、客户端&#xff1a; 2.服务端&#xff1a;三、业务实践&#xff1a;能否做到精准投递&#xff1f; 总结 前言…...

使用IntelliJ IDEA查看接口的全部实现方法

在大型Java项目中&#xff0c;经常会使用接口和抽象类进行代码设计。为了更好地了解代码结构和功能&#xff0c;我们需要快速查看一个接口的所有实现类。IntelliJ IDEA提供了一些方便的方法来实现这一目标。 1. 点击查看接口的实现子类 在IDEA中&#xff0c;你可以轻松地查看…...

阿里云幻兽帕鲁服务器操作系统类型怎么选择?

使用阿里云服务器搭建幻兽帕鲁操作系统类型选Windows还是Linux&#xff1f;如果对Linux熟悉就选择Linux&#xff0c;相对于windows&#xff0c;Linux更少占用系统资源&#xff1b;如果对Linux不熟悉&#xff0c;首选Windows。事实上&#xff0c;阿里云提供的幻兽帕鲁服务器通过…...

Codeforces Round 927 (Div. 3) LR-remainders的题解

原题描述&#xff1a; C.LR-remains 每次测试时限&#xff1a;2 秒 每次测试的内存限制&#xff1a;256 兆字节 输入&#xff1a;标准输入 输出&#xff1a;标准输出 样例1输入&#xff1a; 4 4 6 3 1 4 2 LRRL 5 1 1 1 1 1 1 LLLLL 6 8 1 2 3 4 5 6 RLLLRR 1 10000 1000…...

HarmonyOS—@Observed装饰器和@ObjectLink嵌套类对象属性变化

Observed装饰器和ObjectLink装饰器&#xff1a;嵌套类对象属性变化 概述 ObjectLink和Observed类装饰器用于在涉及嵌套对象或数组的场景中进行双向数据同步&#xff1a; 被Observed装饰的类&#xff0c;可以被观察到属性的变化&#xff1b;子组件中ObjectLink装饰器装饰的状…...

The method toList() is undefined for the type Stream

The method toList() is undefined for the type Stream &#xff08;JDK16&#xff09; default List<T> toList() { return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray()))); }...

vue+element (el-progress)标签 隐藏百分比(%) ,反向显示 ,自定义颜色, demo 复制粘贴拿去用

1 效果: 2 页面代码: <el-row :gutter"10" ><el-col :span"12"><el-card ><div class"fourqu"><div><span slot"title">{{推送任务TOP5}}</span></div></div><div class&…...

Android轻量级进程间通信Messenger源码分析

一. 概述 Android中比较有代表性的两大通信机制&#xff1a;1. 线程间Handler通信 2. 进程间Binder通信&#xff0c;本篇文章中我们在理解AIDL原理的基础上来解读一下Messenger的源代码&#xff0c; 并结合示例Demo加深理解。 在看本篇文章前&#xff0c;建议先查阅一下笔者的…...

C#开发AGV地图编辑软件

C#自己开发AGV地图编辑软件&#xff1a; 1、自由添加和删除站点、停车位、小车、运行路径。 2、编辑得地图以XML文件保存。 3、导入编辑好地图的XML文件。 4、程序都是源码&#xff0c;可以直接在此基础上进行二次开发。 下载链接&#xff1a;https://download.csdn.net/d…...

嵌入式学习day22 Linux

文件IO: 1. lseek off_t lseek(int fd, off_t offset, int whence); 功能: 重新设定文件描述符的偏移量 参数: fd:文件描述符 offset:偏移量 whence: SEEK_SET 文件开头 …...

不确定性问题的论文笔记

Statistics starting from 01/2024, 仅列出了优秀工作中的一部分 每一年的排列顺序: CVPR, ICLR, ECCV, ICCV, ICML, AAAI, TPAMI&#xff0c;TIP&#xff0c;Arxiv 等 每周更新 2024 论文信息速览笔记是 否 已精读精读笔记Shao W, Xu Y, Peng L, et al. Failure Detection fo…...

C语言推荐书籍

本书详细讲解了C语言的基本概念和编程技巧。全书共17章。第1章、第2章介绍了C语言编程的预备知识。第3章&#xff5e;第15章详细讲解了C语言的相关知识&#xff0c;包括数据类型、格式化输入/输出、运算符、表达式、语句、循环、字符输入和输出、函数、数组和指针、字符和字符串…...

基于uniapp微信小程序的汽车租赁预约系统

随着现代汽车租赁管理的快速发展&#xff0c;可以说汽车租赁管理已经逐渐成为现代汽车租赁管理过程中最为重要的部分之一。但是一直以来我国传统的汽车租赁管理并没有建立一套完善的行之有效的汽车租赁管理系统&#xff0c;传统的汽车租赁管理已经无法适应高速发展&#xff0c;…...

ClickHouse 基础(一)

官网 ClickHouse release 24.1, 2024-01-30 以毫秒为单位查询数十亿行 ClickHouse是用于实时应用和分析的最快、资源效率最高的开源数据库。 安装ClickHouse 使用ClickHouse&#xff0c;你有三个选择: ClickHouse云:官方ClickHouse作为一项服务&#xff0c;-由ClickHouse的创…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

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

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

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

【Java】Ajax 技术详解

文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...

英国云服务器上安装宝塔面板(BT Panel)

在英国云服务器上安装宝塔面板&#xff08;BT Panel&#xff09; 是完全可行的&#xff0c;尤其适合需要远程管理Linux服务器、快速部署网站、数据库、FTP、SSL证书等服务的用户。宝塔面板以其可视化操作界面和强大的功能广受国内用户欢迎&#xff0c;虽然官方主要面向中国大陆…...