12342的话就删除4，也就是说当出现一个逆序对时候，删除前面那个可以获取到更小的数字，用栈维持单调栈，
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
| class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> s;
for(auto ch : num)
{
while(k && !s.empty() && s.back() > ch)
{
s.pop_back();
--k;
}
s.push_back(ch);
}
while(k--)
s.pop_back();
string ret;
bool leadingZero{ true };
for(auto ch : s)
{
if(leadingZero && ch == '0')
continue;
if(ch != '0')
leadingZero = false;
ret += ch;
}
return ret.empty() ? "0" : ret;
}
};
|