LeetCode 402. Remove K Digits

1641 ワード

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.

  • 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.
    class Solution {
    public:
        string removeKdigits(string a, int k) {
    	stack s1;
        int n;
    	for(int i = 0;a[i] != '\0';i++)
        {
            n = i+1;
        }
        if(n == k)
            return "0";
    	int count = k;
    	s1.push('0'); //      
    	s1.push(a[0]);
    	for(int i = 1;i < n;++i)
    	{
    		while(s1.top() > a[i] && count > 0)
    		{
    			s1.pop();
    			count--;
    		}
    		s1.push(a[i]);
    		
    	}
    	while(count--)
    	{
    		s1.pop();
    	}
    	char c[n-k+1];
    	c[n-k] = '\0';
    	for(int i = n-k-1;i >= 0;i--)
    	{
    		c[i] = s1.top();
    		s1.pop();
    	}
        int i = 0;
        char *p = c; 
        while(c[i++] == '0')
            p = &c[i];
        if(i == n-k+1)
            return "0";
        else
    	    return p;
        }
    };