LeetCode 解题报告 (402,316,321)-- 删除字符串 k 个字符使剩余字符串取最值

发表于 标签 ，

本文主要讲述如何解决这一类问题：给定一个含有数字或英文字母的字符串，从中删除 k 个字符，使得剩下的字符取得最小值或最大值。数字的大小的比较容易理解，而字母的大小则是按照其 ASCII 码来排列，如 'abc'>'abd'。

下面以 LeetCode 上的几道题目为例进行讲解： 402. Remove K Digits 316. Remove Duplicate Letters 321. Create Maximum Number

解决这类题目的关键点是借助栈这种数据结构，遍历给出的字符串，将当前元素与栈顶元素比较大小，从而决定是否要将当前元素出栈，最后栈内剩余元素就是所需结果。这只是大致的过程，具体的步骤需要根据题目的具体要求。下面以上面的题目为例讲解

402. Remove K Digits 这个题目要求去掉给定字符串（全是数字）中的 k 个字符，使得剩余的字符串表示的数字最小。根据我们上面说到的大致流程，这道题目的解决步骤如下：

1. 创建一个栈，以及记录当前已经删除的字符数量的计数器 2. 对于字符串中的每个字符，记为当前字符，先将其与栈顶元素比较（假如栈不为空），若当前字符小于栈顶元素，则将栈顶元素出栈，将计数器加一，重复该操作直到栈为空或栈顶元素小于当前元素或计数器等于 k，然后将当前元素入栈

具体的 python 代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        stack = []
        remain = len(num) - k
        for dig in num:
            while k and stack and stack[-1] > dig:
                stack.pop()
                k -= 1
            stack.append(dig)
        return ''.join(stack[:remain]).lstrip('0') or '0'

最后 return 语句之所以要选取前 len(num) - k 个字符是因为 result 中可能会有多余这个数目的字符，如对于从小到大排列的字符串就会出现这种情况，另外还需要处理掉前缀 0 以及当结果为空的时候返回 '0'

316. Remove Duplicate Letters 的要求跟 402. Remove K Digits 类似，只是这次要求删除的是字母，而且每个字符要求出现一次且只能出现一次。

解决的思路跟上面的一样，只是因为要求每个字符出现且只出现一次，在入栈和出栈的时候需要特殊的限制条件。具体步骤入下

1. 创建一个栈，记录每个字符在字符串中出现的次数的 table 2. 对于字符串中的每个字符，先判断其是否已在栈内，若已在栈内，将 table 中对应该字符的计数减去 1，然后跳到字符串的下一字符；若不在栈内，栈顶元素大于当前字符且 table 内剩余的栈顶元素的个数大于 1 时，将栈顶元素出栈，重复该操作直到栈为空或栈顶元素小于当前元素，然后将当前字符入栈

实现的 python 代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        result, stored, count = [], set(), {}
        for char in s:
             count.setdefault(char, 0)
             count[char] += 1
        for char in s:
            if char in stored:
                count[char] -= 1
                continue
            else:
                while result and result[-1] > char and count[result[-1]] > 1:
                    count[result[-1]] -= 1
                    stored.remove(result.pop())
                stored.add(char)
                result.append(char)
        return ''.join(result)

321. Create Maximum Number 题目要求与上面两题相比不是相似性不高，但是也是利用这种思想的，题目要求从两个数组 nums1 和 nums2 中共选出 k 个数字，从而使得这 k 个数字组成的数最大。

解决方法就是先从 nums1 中选出 i 个数（0 <= i <= k）使得这 i 个数组成的数字最大，然后从 nums2 中选出 k-i 个数，同样使得这 k-i 个数组成的数字最大，最后将从两个数组中抽出的最大数字合并起来。

实现的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        return max(self.merge(self.single_max(nums1, i), self.single_max(nums2, k-i)) for i in xrange(k+1) if i <= len(nums1) and (k-i) <= len(nums2))


    def single_max(self, nums, k):
        drop = len(nums) - k
        stack = []
        for digit in nums:
            while drop and stack and stack[-1] < digit:
                stack.pop()
                drop -= 1
            stack.append(digit)
        return stack[:k]

    def merge(self, nums1, nums2):
        return [max(nums1,nums2).pop(0) for _ in xrange(len(nums1)+len(nums2))]

上面的代码中 max(num1, num2) 中的 nums1 和 nums2 是两个数组，比较的时候回比较两个数组的第一个元素，然后返回第一个元素较大的数组，若第一个元素相等，则比较第二个元素，依此类推；pop (0) 则是删除并返回下标为 0 的元素，也就是第一个元素。通过这些语法可以简化代码