402. Remove K Digits
題意
給定一個字串 num
代表數字,移除 k
個字元,讓數字維持最小
限制
-
1 <= k <= num.length <= 105
-
num
consists of only digits. -
num
does not have any leading zeros except for the zero itself.
思考
-
要讓數字最小,要盡量從左方移除較大的數字
-
盡量組成遞減數列
-
monotonic stack
-
-
若開頭是0則直接移除,才不會組成不合法的數字
Solution
class Solution {
public:
string removeKdigits(string num, int k) {
const int n = num.size();
string s = "";
for (int i = 0; i < n; i += 1) {
while (k > 0 && !s.empty() && s.back() > num[i]) {
s.pop_back();
k -= 1;
}
s.push_back(num[i]);
if (s.size() == 1 && s.back() == '0') {
s.pop_back();
}
}
while (k > 0 && !s.empty()) {
s.pop_back();
k -= 1;
}
return s.empty() ? "0" : s;
}
};