给出一串数，对于每一位，输出从第一个数到当前数的最长不降子序列长度，巧妙利用stack，参考了discussion
维护一个单调不降的stk，对于每一位的数字，二分stk，若该数字比所有stk里的数都大，则append到末尾，否则替换stk里位于该数右边的一个数（因为要求单调不降而不是单调增），二分直接用python的bisect_right
1 #1964
2 #Runtime: 1442 ms (Beats 33.33%)
3 #Memory: 32 MB (Beats 100%)
4
5 class Solution(object):
6 def longestObstacleCourseAtEachPosition(self, obstacles):
7 """
8 :type obstacles: List[int]
9 :rtype: List[int]
10 """
11 stk, ans = [], []
12 for i in obstacles:
13 j = bisect_right(stk, i)
14 if j == len(stk):
15 stk.append(i)
16 else:
17 stk[j] = i
18 ans.append(j + 1)
19 return ans