給出一串數，對于每一位，輸出從第一個數到當前數的最長不降子序列長度，巧妙利用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