原題鏈接在這里:https://leetcode.com/problems/remove-k-digits/description/
題目:
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:
- The length of?num?is less than 10002 and will be ≥?k.
- The given?num?does not contain any leading zero.?
leetcode all in one,Example 1:
Input: num = "1432219", k = 3 Output: "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 = 1 Output: "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 = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
題解:
利用stack 保存從頭到尾iterate input num string的char, 若當前char 比stack頂小就一直pop棧頂直到 去掉的數等于k了或者棧頂的元素更小.
leetCode,然后從頭到尾找到第一個非0的位置 往后掃剩余digit長度的char.?
掃過的0也應該count在剩余digit長度中,只不過不會顯示在結果string里.
Time Complexity: O(n). n = num.length().
Space: O(n).
AC Java:
1 class Solution { 2 public String removeKdigits(String num, int k) { 3 if(num == null || num.length() == 0){ 4 return num; 5 } 6 7 int len = num.length(); 8 int remainDigits = len-k; 9 char [] stk = new char[len]; 10 int top = 0; 11 for(int i = 0; i<len; i++){ 12 char c = num.charAt(i); 13 while(top>0 && c<stk[top-1] && k>0){ 14 top--; 15 k--; 16 } 17 18 stk[top++] = c; 19 } 20 21 // 找到第一個不為0的index 22 int ind = 0; 23 while(ind<remainDigits && stk[ind]=='0'){ 24 ind++; 25 } 26 return ind == remainDigits ? "0" : new String(stk, ind, remainDigits-ind); 27 } 28 }
leetcode中文、類似Create Maximum Number.