Leetcode 901. Online Stock Span(栈)


题目来源:https://leetcode.com/problems/online-stock-span/description/

标记难度:Medium

提交次数:1/1

代码效率:19.81%

题意

给定一个整数数组,为每一个数求出以它为结尾的满足这一条件的连续子数组的最大长度:其余的数都比它更小。

分析

比赛的时候显然我没有做出来这道题,心态崩了。我大概是想出了一个合理的离线方法,但这道题强制要求在线。我当时只能想出O(n^2)的暴力在线方法,没看出来什么递推的方法简化时间复杂度。或者说我就没见过这个类型的题目……


离线算法1:排序

如果这道题是离线的话,我想出了这样一种做法:

  • 首先把所有数和它们原来的index进行排序
  • 然后按数值大小遍历所有数,并维护一棵存放index的BST;对于每个数,在该BST中查找自己的index的前驱,前驱和自己的index之间的距离(有相同数值时需要特殊处理);最后把自己的index插入树中

时间复杂度是O(n * log(n))

离线算法2:递归

事实上通过仔细观察是可以进行一定程度的递推的。这一点我觉得题解就写得不错。假定当前的数组是这样的:

1
2
array = [11, 3, 9, 5, 6, 4]
len = [ 1, 1, 2, 1, 2, 1]

对于下一个元素x

  • 如果x < last,则len[x] = 1
  • 如果x == last,则len[x] = len[last] + 1
  • 如果x > last,则需要在前面的元素中找到比x大的最后一个元素。不过,因为x > last,所以需要找到的元素必然也比last更大。所以对于每一个元素,只有前面比它更大的元素在递推中才有意义。

但是这么想还不够好,因为显然元素的大小可能是随机的,对于不同的元素,“前面比它更大的元素”这个集合在动态变化,并不能直接进行递推。

再重新观察一下上面的例子,查看一下每个元素覆盖的具体子序列:

1
2
3
4
5
6
7
array =     [ 11, 3 , 9 , 5 , 6 , 4 ]
Element 11 +
Element 3 +
Element 9 + +
Element 5 +
Element 6 + +
Element 4 +

一个有趣的问题是,可以试图从这些元素中选择出一部分,使得它们各自的子序列恰好可以拼成这个完整的数组。选择的方法是,先选出数组中最大的数,再选出数组中在这个数之后最大的数,再选出在这个数之后最大的数……直到选到最后一个数。在这个例子中,选出的就是11, 9, 6, 4。它们对应的子序列的长度就是到前一个数的距离。

那么在选出来的数中间的那些数怎么办呢?事实上,这个时候我们已经得到了一个子问题的结构。通过上述选择过程可以看出,夹在选出来的数中间的数必然比两边的数小,也就是说它们的子序列长度和周围的数没有任何关系。

但这仍然是一个离线算法,而且时间复杂度也很成问题。

在线算法:栈

事实上我刚才写了那么多字,主要是为了试图解释这个算法为何是合理的——因为我看到题解的时候,实在是不知道为什么能这么做。不过现在我觉得我已经可以给出一个合理的答案了。刚才已经得到了一个子问题的结构。虽然看起来好像一次选择可能会把数组划分成好几个子问题(事实上也是这样),但实际上并没有把这个问题递归化的必要——因为分割前的元素的结果不依赖于子问题的结果,对吧。所以只要能合理地划分子问题,就可以用任意合理的顺序来解决子问题——比如顺序解决。

我想,栈的作用就是这样的。在加入每个元素之前,把比它小的元素都弹出来。此时栈中实际上顺序保存了一些子问题的元素。(我发现很难描述到底保存了哪些元素……)弹出的过程相当于解决了当前层次的所有子问题。题解中只说“关注递增的元素”,但并没有解释怎么关注递增的元素这个问题。[1]

PS. 这道题和Leetcode 739基本上是一样的,看来我还是见得少了。

2018.9.16 UPDATE:通过今天的比赛题Leetcode 907,我意识到了一个问题,这个算法比我想象得要更强一些。对于被某个数从栈中弹出的数而言,它右侧第一个比它大的数就是这个数。所以一个方向的一次使用栈的操作可以同时解决两侧的问题。

代码

只实现了在线算法(显然只能这样)。

在线算法:栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class StockSpanner {
private:
stack<pair<int, int>> s;

public:
StockSpanner() { }

int next(int price) {
int sum = 1;
while (!s.empty() && s.top().first <= price) {
sum += s.top().second;
s.pop();
}
s.emplace(price, sum);
return sum;
}
};

  1. Leetcode 901 Solution


 评论