leetcode 402. Remove K Digits | 402. 移掉 K 位数字（单调栈）

雨点打透心脏的1/2处 2022-08-29 09:45 115阅读 0赞

## 题目 ##

[https://leetcode.com/problems/remove-k-digits/][https_leetcode.com_problems_remove-k-digits]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

本题考察对问题的抽象能力，多写几个例子可以发现，这是一个单调栈问题，维护一个单调不减栈。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public String removeKdigits(String num, int k) { 
            Stack<Integer> stack = new Stack<>(); // 单调(不减)栈
            int del = 0; // 已删除digits数量
            int i;
            for (i = 0; i < num.length() && del < k; i++) { 
                while (!stack.isEmpty() && del < k && stack.peek() > num.charAt(i) - '0') { 
                    stack.pop();
                    del++;
                }
                stack.push(num.charAt(i) - '0');
            }
    
            StringBuilder sb = new StringBuilder();
            // 调整单调栈容量至不大于num.length-k
            while (del < k) { 
                stack.pop();
                del++;
            }
            // 拼接stack所有值，并将num剩余部分全部顺延拼接
            while (!stack.isEmpty()) { 
                sb.insert(0, stack.pop());
            }
            sb.append(num.substring(i));
            // 删除前导0
            int j;
            for (j = 0; j < sb.length(); j++) { 
                if (sb.charAt(j) != '0') { 
                    break;
                }
            }
            return sb.substring(j).length() > 0 ? sb.substring(j) : "0";
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_remove-k-digits]: https://leetcode.com/problems/remove-k-digits/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/1e4d3671d60147f0bd3951248e2a0baa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/6ecc67a7504246b5bfe177867ba3a879.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/9d5b86765e244792a15518c3a5a443c0.png