Leetcode 5: stack

Posted on | | Visitors: | views

本文整理Leetcode上与stack有关的题目

Sum of Subarray Minimums

  • Problem: Given an array of integers A, find the sum of min(B), where B ranges over every substring of A. Since the answer may be large, return the answer modulo 10^9 + 7.
  • Example: Input [3,1,2,4], output 17. Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
  • Link: https://leetcode.com/problems/sum-of-subarray-minimums/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # From https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170776/Python-Simple-Stack-O(n)-Solution-10-lines
    # 算法的设计是找到每个数能覆盖的最小范围，即在该范围内这个数是最小的。比如3124中，3的范围是|3|，1的范围是|3124|，那么第i位上的数d对总和的贡献是d * (i - 左边界) * (右边界 - i)，即含有d的subarray数量。具体而言，用一个单调栈来实现这一功能，元素入栈后，只有右边界才会使之弹出。

    class Solution:
        def sumSubarrayMins(self, A):
            res = 0
            stack = []  #  non-decreasing 
            A = [float('-inf')] + A + [float('-inf')]
            for i, n in enumerate(A):
                while stack and A[stack[-1]] > n:
                    cur = stack.pop()
                    res += A[cur] * (i - cur) * (cur - stack[-1]) 
                stack.append(i)
            return res % (10**9 + 7)

Smallest Subsequence of Distinct Characters

  • Problem: Return the lexicographically smallest subsequence of text that contains all the distinct characters of text exactly once.
  • Example: Input ‘ecbacba’, output ‘eacb’. Explanation: from left to right, we can generate candidate subsequences as ‘ecba’, ‘ecab’, ‘ebac’, ‘ebca’, ‘eacb’. The smallest one is ‘eacb’.
  • Link: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # 这个题目不太好理解，意思是在给定字符串中，抽取出所有字母有且仅有一次出现的全部子序列；把这些子序列按照字典序进行排列，返回最小的那个。

    # 一个常规的思路是读取所有的字母，按字典序生成子串，再逐个看是否为给定字符串的自序列。
    # 此方法的问题就是26个字母可以生成26!种组合，复杂度上升很快
    class Solution:
        def smallestSubsequence(self, text):
            import itertools
            distinct = set(text)
            length1, length2 = len(text), len(distinct)

            for ll in sorted([''.join(l) for l in itertools.permutations(distinct, len(distinct))]):
                pointer1, pointer2 = 0, 0
                while pointer1 < length1 and pointer2 < length2:
                    if text[pointer1] == ll[pointer2]:
                        pointer2 += 1
                        if pointer2 == length2:
                            print(ll)
                    pointer1 += 1

    # 好的方法是用单调栈：来自https://leetcode.com/badgergo/大神
    # 思路是：从左往右扫描，当遇到新的字母小于栈顶元素时，这说明我们可以弹出栈顶加入该元素来获得更小的序列。但要注意的是，栈顶元素必须在后续待扫描序列中存在，否则就不满足含有全部字母的条件。
    class Solution:
        def smallestSubsequence(self, text):
            text = tuple(map(ord, text))
            right = {num : i for i, num in enumerate(text)}
            seen = set()
            stack = []
            for i, num in enumerate(text):
                if num not in seen:
                    while stack and num < stack[-1] and right[stack[-1]] > i:
                        seen.remove(stack.pop())
                    stack.append(num)
                    seen.add(num)
            return ''.join(map(chr, stack))