LeetCode 解题报告 (739,901,907)- 线性时间寻找数组中各个元素作为最值的最大范围

题目有点拗口，其实就是给定一个数组，要求给出某个元素作为最小值或最小值的那些 continous subarrays 中最长的长度，如对于数组 [1, 2, 5, 6], 元素 5 作为最大值的 continous subarrays 有三个： [5], [2, 5], [1, 2, 5]，长度最长的是 3。遍历的解法找出一个元素要 \(O(n)\) 的时间复杂度，找出所有元素则需要 \(O(n^2)\) 的时间复杂度，而通过栈能够在 \(O(n)\) 的时间复杂度内解决这个问题。

下面这两个题目都直接用到了这种解法

739. Daily Temperatures 901. Online Stock Span

以 901. Online Stock Span 为例，如下所示，其实题目就要找出某个元素作为最大值时 subarray 的最大长度，且这个 subarray 是有方向的，即只能从当前元素往左延伸

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

暴力的遍历需要 \(O(n^2)\) 的时间复杂度，那通过栈如何在 \(O(n)\) 的时间复杂度解决这个问题呢？

首先创建一个空栈用于存储每个元素的下标，从左到右遍历数组中的元素，对于当前元素，假如栈为空或栈顶元素大于当前元素，则将当前元素入栈，否则一直出栈直到栈为空或栈顶元素大于当前元素，这样做将左边比当前元素小的元素都出栈，最后栈顶元素（如果有）和当前元素之间的距离就是要求的距离，如果栈为空，则当前元素是当前遍历的所有元素中最大的，其 下标 + 1 便是要求的距离。

由于每个元素最多会被入栈一次和出栈一次，因此其时间复杂度便是 \(O(n)\), 其减小时间复杂度的原理其实就是通过出栈减少了元素比较的次数，比如说对于当前元素 e，出栈了 k 个元素，那后面如果有个元素比 e 大，肯定也比出栈的 k 个元素要大，因此无需进行比较，而这 k 个元素已经出栈了，因此减少了这 k 次的比较。

另外，需要注意的是，由于要求的是距离，因此栈存储的是元素的下标，比较元素大小是通过原数组加下标即可。

因此 901 题目的 python 代码如下，也有 c++ 版本 和 go 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class StockSpanner(object):

    def __init__(self):
        self.nums = []
        self.stack = []
        self.idx = 1

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        while self.stack and self.nums[self.stack[-1]-1] <= price:
            self.stack.pop()
        self.nums.append(price)
        span = self.idx-self.stack[-1] if self.stack else self.idx
        self.stack.append(self.idx)
        self.idx += 1
        return span

739.Daily Temperatures 的题目原理是一样的，只是要求的是最小元素往右的最长 subarray，解法同上，只是此时需要从后往前遍历数组了，具体的代码可见: python 版本，c++ 版本，go 版本

拓展

上面两个题目是比较明确要求出各个元素作为最小值或最大值时的最长 subarray 的长度，但是有些问题不会直接要求这么求解。比如说题目 907. Sum of Subarray Minimums, 题目要求的是求出所有 subarray 中最小元素的和，下面是一个简单的例子

1
2
3
4

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.

通过穷举法求解的时间复杂度显然太高了，但是我们可以换一个角度来求解这个问题，就是只要求出某个元素作为最小值的 subarray 个数，那么该元素乘上 subarray 个数便是这个元素对最终的结果的贡献值，比如说比如说对于某个长度为 n 的数组 A, 其各个元素作为最小值的 subarray 个数分别是 f[0], f[1].....f[n-1], 则最终结果为

\[\begin{align} \sum_{i=0}^{n-1} A[i]f[i] \end{align}\]

那么现在的问题就是要求出各个元素作为最小值的 subarray 个数，这就要用到了我们前面提到的通过栈求解的方法了，而且要分别往左和往右求出 subarray 的长度。

对于当前元素 A[i], 将当前值作为最小值，分别往左和往右求出的 subarray 长度记为 left 和 right，则包含 A[i] 作为最小值的 subarray 个数为： f[i] = left * right

实现的 python 代码如下，也可参考 c++ 版本 和 go 版本

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 sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        s, left = [], []
        for i in xrange(n):
            while s and A[s[-1]] >= A[i]:
                s.pop()
            left.append(i - s[-1] if s else i + 1)
            s.append(i)

        s, right = [], []
        for i in xrange(n - 1, -1, -1):
            while s and A[s[-1]] > A[i]:
                s.pop()
            right.append(s[-1] - i if s else n - i)
            s.append(i)
    return sum(A[i] * left[i] * right[n-i-1] for i in xrange(n)) % (10**9 + 7) 

上面的思路就是分别从左到右和从右到左获取 left 和 right 这两个表示 subarray 数量的数组，需要注意的是，获取 left 数组是用的比较条件是 A[s[-1]] >= A[i], 但是获取 right 数组时用的是 A[s[-1]] > A[i]; 这里以一个例子简介会比较方便，假如说对于数组 [71,55,82,55], 如果两个比较条件都采用 >=，那么 [55,82,55] 这个 subarray 会被重复计算两次， 如果都采用 >, [55,82,55] 则不会被计算，因此一定要有一个采用 >=, 而另一个采用 >。

这里其实也引出另外一个非常重要的思想，就是分别求出每个元素对最终结果的贡献，然后累加起来便是最终的结果，在上面的问题即是求出某个元素作为最小值的 subarray 个数，那么该元素乘上 subarray 个数便是这个元素对最终的结果的贡献值。且这一类问题一般都跟 subarray、 subsequence 相关，比如说 828. Unique Letter String 和 891. Sum of Subsequence Widths 都是通过这种思想来解决的

首先看问题 828. Unique Letter String，题目要求出所有的 subarray 中的 unique characters 的数量，遍历的时间复杂度是 \(O(n^3)\), 但是采用上面提到的思想，可以分别求出每个元素作为 unique character 时的 subarray 的数量，然后累加起来即可，这样的时间复杂度变为了 \(O(n^2)\), AC 的 python 代码如下， 另外也可参考 c++ 版本 和 go 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def uniqueLetterString(self, S):
        """
        :type S: str
        :rtype: int
        """
        result = 0
        MOD = 1000000007
        for i in xrange(len(S)):
            left, right = i - 1, i + 1
            while left >=0 and S[left] != S[i]:
                left -= 1
            while right < len(S) and S[right] != S[i]:
                right += 1
            result += ((i - left) * (right - i)) % MOD
            result %= MOD
        return result

问题 891. Sum of Subsequence Widths 与前面的不同，前面的都是连续的 subarray， 而这里是可以不连续的 subsequence，题目要求出每个 subsequence 中最大值和最小值的差，然后求和得到最终的结果。同样采用上面的思想，求出某个元素 A[i] 作为最小值的 subsequence 的数量 n1, 作为最大值的 subsequence 的数量 n2, 则 A[i] 对最终结果的贡献是 n2 * A[i] - n1 * A[i]。但是 n1、n2 不能像之前一样分别往左往右延伸获取了，这里有一个很重要但是很容易被忽略的事实：数组的顺序不影响最终的结果。因此可以将数组进行排序，n1 就是当前元素左边元素的一个组合数量了，n2 同理。AC 的 python 代码如下， 在实现中计算 \(2^i\) 使用位移操作即 1<<i 而不是直接计算，否则会导致超时

1
2
3
4
5
6
7
8
9
10

class Solution(object):
    def sumSubseqWidths(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        MOD = 1000000007
        n = len(A)
        A.sort()
        return sum((((1 << i) - (1 << (n-i-1))) * A[i]) % MOD for i in xrange(n)) % MOD

小结

本文主要介绍了两个重要的思想，其中一个是通过栈在线性时间内求解数组中某个元素作为最小值（或最大值）的最长 subarray，代表性的题目有 739. Daily Temperatures、901. Online Stock Span 和 907. Sum of Subarray Minimums；另外一个重要的思想是分别求出每个元素对最终结果的贡献，然后累加起来便是最终的结果，代表性的题目有 828. Unique Letter String、891. Sum of Subsequence Widths 和 907. Sum of Subarray Minimums。