給出一串?dāng)?shù)，對(duì)于每一位，輸出從第一個(gè)數(shù)到當(dāng)前數(shù)的最長(zhǎng)不降子序列長(zhǎng)度，巧妙利用stack，參考了discussion
維護(hù)一個(gè)單調(diào)不降的stk，對(duì)于每一位的數(shù)字，二分stk，若該數(shù)字比所有stk里的數(shù)都大，則append到末尾，否則替換stk里位于該數(shù)右邊的一個(gè)數(shù)（因?yàn)橐髥握{(diào)不降而不是單調(diào)增），二分直接用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