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

2024-02-19 06:52

本文主要是介绍【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位数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/723838

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数