今天的每日一题是 LC402 移除 K 位数字,最终看题解完成，记录一下思路。
描述
题目的描述如下
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
分析
这个题的关键是判断那一些位的数字需要被丢弃，以此组成一个最小的数字。
所以我们需要：
1.数字大小的比较。
2.怎么判断数字是否需要被丢弃
数字大小的比较
我们判断两个数字大小时，是通过其不相同的最高位数字大小来比较的。
1.首先判断数的位数，相同则进行下一步。否则位数多的大。
a=12xxx,b=11xxxx,显然 a<b
2.位数相同时，一位一位比较，从高到低。相同的则跳过，直到有一位能分出大小。
a=12xxxxx,b=13xxxxx,此时由于第二位 2<3,所以有 a>b
判断数字是否丢弃
丢弃条件
贪心策略:
对数字$D_1D_2…D_x$,如果有位置$i$,使得$D_i<D_{i-1}$,此时要把$D_{i-1}$丢弃。
如果不存在,说明整个数字序列单调不降（像 123456789），此时删去最后一个数字即可。
下面对题目简单的模拟:
设 num=1432219,n=3,遍历 num,每次只与左边数的进行比较，如果比左边大则放入，反之则丢弃左边数字，并继续和左边的数比较、放入、丢弃步骤。
最后的结果必然是数字序列单调不降，所以我们使用一个单调栈来保存未被丢弃的数字。
如果此时丢弃的数位依旧不足，则丢弃最后的几位数字。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
/*
* @lc app=leetcode.cn id=402 lang=cpp
*
* [402] 移掉K位数字
*/
// @lc code=start
// 单调栈+贪心
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> ret;
for (auto& ch : num) {
while (ret.size() > 0 && k && ret.back() > ch) {
ret.pop_back();
k--;
}
ret.push_back(ch);
}
// 处理未处理的k,此时数据已是单调增，去除最后几位
while(k--){
ret.pop_back();
}
string ans = "";
bool begWithZero = true;
for (auto& digit : ret) {
if (digit == '0' && begWithZero) {
continue;
}
begWithZero = false;
ans += digit;
}
return ans == "" ? "0" : ans;
}
};
// @lc code=end
|
参考
LC402
官方题解
单调栈