【单调栈】2024D-找最小数
【单调栈】2024D-找最小数
[P2652] 【单调栈】2024D-找最小数
本题练习地址：https://www.algomooc.com/problem/P2652
题目描述
给一个正整数 NUM1，计算出新正整数 NUM2。NUM2 为 NUM1 中移除 N 位数字后的结果，需要使得 NUM2 的值最小。
输入
- 输入的第一行为一个字符串，字符串由
0-9字符组成，记录正整数NUM1，NUM1长度小于32。 - 输入的第二行为需要移除的数字的个数，小于
NUM1长度。
输出
输出一个数字字符串，记录最小值 NUM2。
示例一
输入
2615371
4输出
131说明
移除 2、6、5、7 这四个数字，剩下 1、3、1 按原有顺序排列组成 131 为最小值。
示例二
输入
12345
2输出
123示例三
输入
10345
2输出
034解题思路
注意，本题和LC402. 移掉K位数字完全一致。
对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小。
例如，对于两个五位数，A = 1axxx，B = 1bxxx，如果 a > b则存在A > B。
贪心地思考这个问题，为了使得剩下的数字尽可能地小，我们肯定希望位于前面的大的数字被尽量删掉。
换句话说，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
假设我们从左到右正序遍历原数字（字符串形式）中的每一个数字字符ch，如果当前字符比之前遍历过遇到的字符更小，则之前遇到过的字符应该被当前这个更小的字符顶替。
这些之前遇到过的更大字符，显然可以用单调栈来储存。即如下代码
stack = list()
for ch in NUM1:
while len(stack) and ch < stack[-1]:
stack.pop()
stack.append(ch)同时，由于题目规定了最多删除的次数n，因此我们还需要控制删除的次数。
可以需要构建一个变量rest_n，来表示还剩下多少次可以进行的删除操作。
因此，出栈条件除了常规的len(stack)和ch < stack[-1]，还要再加上一条rest_n > 0。
同时，一旦进入出栈的while循环，就得进行rest_n的递减，表示消耗了一次删除的机会。
故整个单调栈算法的核心代码为
rest_n = n
stack = list()
for ch in NUM1:
while len(stack) and ch < stack[-1] and rest_n > 0:
stack.pop()
rest_n -= 1
stack.append(ch)注意到，删除了n次后的数字长度一定为len(NUM1)-n，但是单调栈中最终的元素长度并不一定是len(NUM1)-n，即n次删除机会没有用完，rest_n在退出for循环之后没有降为0。（譬如示例二）
故最终单调栈中的有效数字仅为前len(NUM1)-n个元素，最终取stack[:len(NUM1)-n]作为答案。
代码
Python
# 题目：2024D-找最小数
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：单调栈
# 代码看不懂的地方，请直接在群上提问
NUM1 = input()
n = int(input())
# rest_n 表示剩余的删除次数
rest_n = n
# 构建一个单调栈，
# 单调栈从栈底至栈顶单调递增
# 即大的数字放在栈顶
stack = list()
# 遍历数字字符串NUM1中的每一个字符ch
for ch in NUM1:
# 出栈的情况：
# 1. 栈不为空
# 2. ch小于栈顶元素
# 3. 剩余的删除次数大于0
# 即可以弹出栈顶元素，这样才能使得栈顶元素尽可能小
while len(stack) and ch < stack[-1] and rest_n > 0:
stack.pop()
rest_n -= 1
# 对于每一个ch，都应该入栈
stack.append(ch)
# 删除了n次后的数字长度一定为len(NUM1)-n
# 但是结束循环时，栈中元素不一定恰好为len(NUM1)-n
# 即n次删除机会不一定全部用完，rest_n没有降为0
# 所以取较小的数前 len(NUM1)-n 个数组合成字符串
print("".join(stack[:len(NUM1)-n]))Java
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String NUM1 = scanner.nextLine();
int n = scanner.nextInt();
int rest_n = n;
Stack<Character> stack = new Stack<>();
for (char ch : NUM1.toCharArray()) {
while (!stack.isEmpty() && ch < stack.peek() && rest_n > 0) {
stack.pop();
rest_n--;
}
stack.push(ch);
}
StringBuilder result = new StringBuilder();
int len = NUM1.length() - n;
for (int i = 0; i < len; i++) {
result.append(stack.get(i));
}
System.out.println(result.toString());
}
}C++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
string NUM1;
int n;
cin >> NUM1 >> n;
int rest_n = n;
stack<char> stack;
for (char ch : NUM1) {
while (!stack.empty() && ch < stack.top() && rest_n > 0) {
stack.pop();
rest_n--;
}
stack.push(ch);
}
string result;
int len = NUM1.size() - n;
while (!stack.empty()) {
result = stack.top() + result;
stack.pop();
}
result = result.substr(0, len);
cout << result << endl;
return 0;
}时空复杂度
时间复杂度：O(M)。仅需一次遍历字符串NUM1。
空间复杂度：O(M)。单调栈所占用的额外空间。
M为字符串NUM1的长度。