本文共 2038 字，大约阅读时间需要 6 分钟。
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
Example 1:
Input: num = "1432219", k = 3Output: "1219"Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1Output: "200"Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2Output: "0"Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Approach #1: C++. [brute force]
class Solution {public: string removeKdigits(string num, int k) { int len = num.length(); if (len == k) return "0"; int rmd = len - k; string ans = ""; int idx = 0; for (int i = 0; i < len; i = idx+1) { int temp = INT_MAX; rmd--; for (int j = i; j < len-rmd; ++j) { if (num[j]-'0' < temp) { temp = num[j] - '0'; idx = j; } } ans += to_string(temp); if (ans.length() == len - k) break; } while (ans[0] == '0' && ans.length() > 1) ans = ans.substr(1); return ans; }};
Time complex: O(n^2)
Approach #2: Java. [stack]
class Solution { public String removeKdigits(String num, int k) { int digits = num.length() - k; char[] stk = new char[num.length()]; int top = 0; for (int i = 0; i < num.length(); ++i) { char c = num.charAt(i); while (top > 0 && stk[top-1] > c && k > 0) { top--; k--; } stk[top++] = c; } int idx = 0; while (idx < digits && stk[idx] == '0') idx++; return idx == digits ? "0" : new String(stk, idx, digits-idx); }}
Time complex: O(n).
转载地址：http://trvuz.baihongyu.com/