LeetCode算法题整理（栈篇）Stack

1021. Remove Outermost Parentheses

删除最外层的括号。原题

Input: "(()())(())"
Output: "()()()"
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Input: "(()())(())(()(()))"
Output: "()()()()(())"
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Input: "()()"
Output: ""

方法一：比赛时的丑陋写法。使用索引记录位置坐切片。

def removeOuterParentheses(self, S: str) -> str:
    l = 0
    left = right = 0
    ans = ''
    for i, p in enumerate(S):
        if p =='(':
            left += 1
            if left == 1:
                l = i
        else:
            right += 1
            if left == right:
                ans += S[l+1:i]
                l = i + 1
                left = right = 0
        # print(ans)
    return ans

方法二：优化。

def removeOuterParentheses(self, S: str) -> str:
    ans, opened = [], 0
    for s in S:
        if s == '(' and opened > 0:
            ans.append(s)
        if s == ')' and opened > 1:
            ans.append(s)
        opened += 1 if s=='(' else -1
    return ''.join(ans)

1047. Remove All Adjacent Duplicates In String

每两个相邻的相同字符串可以消掉。类似于连连看。原题

def removeDuplicates(self, S: str) -> str:
    stack = []
    for c in S:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)

1172. Dinner Plate Stacks

有这样一堆栈，每个栈有个容量，可以在指定索引下删除某个栈，每次push时需要在最左的不满的栈。原题

Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

方法一：一开始被题吓到了，竞赛时没做出来，核心思想在于维护一个堆，记录不满的栈。以便插入时可以找到该索引。

class DinnerPlates:

def __init__(self, capacity: int):
    self.c = capacity
    self.q = []
    self.emp = []

def push(self, val: int) -> None:
    if self.emp:
        index = heapq.heappop(self.emp)
        self.q[index].append(val)
    else:
        if self.q and len(self.q[-1])!=self.c:
            self.q[-1].append(val)
        else:
            self.q.append([val])

def pop(self) -> int:
    while self.q:
        if self.q[-1]:
            return self.q[-1].pop()
        self.q.pop()
    return -1

def popAtStack(self, index: int) -> int:
    heapq.heappush(self.emp, index)
    if self.q[index]:
        return self.q[index].pop()
    else:
        return -1

901. Online Stock Span

实时找出数据流中连续的比不大于当前值的个数。原题

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

方法一：<=可以累加。

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        cnt = 1
        while self.stack and self.stack[-1][0] <= price:
            cnt += self.stack.pop()[1]
        self.stack.append((price, cnt))
        return cnt

907. Sum of Subarray Minimums

一个数组所有子数组的最小值的和。

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.

方法一：by@Lee, 没想到可以用stack，实际上和901问题是一样的，对于一个数而言，找到左侧和右侧比它大的数，代表着左侧和右侧所能组成的子数组的长度，就是它在最小值计算里出现的次数。本来想封装一下这个方法，但是计算左侧时条件是>，其实终点不在于顺序，而是=只能有一个，因为如果都按>=计算，相同数字的就会有子数组计算重复了。

def sumSubarrayMins(self, A: List[int]) -> int:
    n, mod = len(A), 10**9+7
    
    left, right, s1, s2 = [0] * n, [0] * n, [], []
    for i in range(n):
        count = 1
        while s1 and s1[-1][0] > A[i]: count += s1.pop()[1]
        left[i] = count
        s1.append([A[i], count])
    for i in range(n)[::-1]:
        count = 1
        while s2 and s2[-1][0] >= A[i]: count += s2.pop()[1]
        right[i] = count
        s2.append([A[i], count])
    
    return sum(a*l*r for a, l, r in zip(A, left, right)) % mod

方法二：Lee又将它写成了一次遍历的形式。

def sumSubarrayMins(self, A):
    res = 0
    s = []
    A = [0] + A + [0]
    for i, x in enumerate(A):
        while s and A[s[-1]] > x:
            j = s.pop()
            k = s[-1]
            res += A[j] * (i - j) * (j - k)
        s.append(i)
    return res % (10**9 + 7)

1299. Replace Elements with Greatest Element on Right Side

根据数组重新生成一个数组，每个元素对应原数组右侧最大的数字。原题

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

方法一：栈

def replaceElements(self, arr: List[int]) -> List[int]:
    stack = [-1]
    for i in range(len(arr)-1, 0, -1):
        if arr[i] < stack[-1]:
            stack.append(stack[-1])
        else:
            stack.append(arr[i])
    return stack[::-1]

方法二：Lee215.

def replaceElements(self, arr: List[int], mx=-1) -> List[int]:
    for i in range(len(arr)-1, -1, -1):
        arr[i], mx = mx, max(mx, arr[i])
    return arr

1249. Minimum Remove to Make Valid Parentheses

删除字符串中多余的括号。原题

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

方法一：比较笨的方法，遍历了两次。

def minRemoveToMakeValid(self, s: str) -> str:

    def helper(arr, sig):
        ans, opened = [], 0
        for c in arr:
            if opened <= 0 and c==sig[1]:
                continue
            if c == sig[0]:
                opened += 1
            elif c == sig[1]:
                opened -= 1
            ans.append(c)
        return ans

    return ''.join(reversed(helper(reversed(helper(list(s), ('(', ')'))), (')', '('))))

方法二：stack、这个方法有点不好理解， 最后的while 循环时为了防止末尾有过多的(

def minRemoveToMakeValid(self, s: str) -> str:
    stack, cur = [], ''
    for c in s:
        if c == '(':
            stack.append(cur)
            cur = ''
        elif c == ')':
            if stack:
                cur = '{}({})'.format(stack.pop(), cur)
        else:
            cur += c
            
    while stack:
        cur = stack.pop() + cur
    return cur

1190. Reverse Substrings Between Each Pair of Parentheses

将括号内的字符串反转。原题

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

方法一：用了和1249一样的解法。

def reverseParentheses(self, s: str) -> str:
    stack, cur = [], ''
    for c in s:
        if c == '(':
            stack.append(cur)
            cur = ''
        elif c == ')':
            if stack:
                cur = '{}{}'.format(stack.pop(), cur[::-1])
        else:
            cur += c
    return cur

1209. Remove All Adjacent Duplicates in String II

将字符串中连续的k的字母全部删除，返回剩余的字符串。原题

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

方法一：这道题虽然ac了，但是复杂度太高了。

def removeDuplicates(self, s: str, k: int) -> str:
    stack = []
    for c in s:
        if len(stack)>=k-1 and all(a==c for a in stack[-k+1:]):
            stack = stack[:-k+1]
        else:
            stack.append(c)
    return ''.join(stack)

方法二：相同字符的记录个数。

def removeDuplicates(self, s: str, k: int) -> str:
    stack = [['#', 0]]
    for c in s:
        if stack[-1][0] == c:
            stack[-1][1] += 1
            if stack[-1][1] == k:
                stack.pop()
        else:
            stack.append([c, 1])
    return ''.join(c*k for c, k in stack)

1475. Final Prices With a Special Discount in a Shop

找出数组中后面元素比当前元素小的差。原题

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. 
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. 
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. 
For items 3 and 4 you will not receive any discount at all.

方法一：暴力法。

def finalPrices(self, prices: List[int]) -> List[int]:
    n = len(prices)
    ans = []
    for i in range(n):
        for j in range(i+1, n):
            if prices[j] <= prices[i]:
                ans.append(prices[i]-prices[j])
                break
        else:
            ans.append(prices[i])
    return ans

方法二：stack. by lee215

def finalPrices(self, A: List[int]) -> List[int]:
    stack = []
    for i, a in enumerate(A):
        while stack and A[stack[-1]] >= a:
            A[stack.pop()] -= a
        stack.append(i)
    return A

739. Daily Temperature

找出比当前元素之后的大的值，计算索引差，没有则是0。原题

方法一：刚刚做完1475的题，一样的解法。

def dailyTemperatures(self, T: List[int]) -> List[int]:
    stack = []
    ans = [0] * len(T)
    for i, t in enumerate(T):
        while stack and T[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

394. Decode String

就是根据括号来重复字符串。原题

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

方法一：使用了两个栈，分别存储数字和字母。

def decodeString(self, s: str) -> str:
    stack, cur, digit, d = [], '', [], ''
    for c in s:
        if c == '[':
            digit.append(d)
            d = ''
            stack.append(cur)
            cur = ''
        elif c == ']':
            cur = stack.pop() + int(digit.pop()) * cur
        elif c.isdigit():
            d += c
        else:
            cur += c
    return cur

方法二：使用一个stack，因为这个规律是有保证的，左括号前一定是数字。

def decodeString(self, s: str) -> str:
    stack, cur, d = [], '', ''
    for c in s:
        if c == '[':
            stack.append(cur)
            stack.append(d)
            d = ''
            cur = ''
        elif c == ']':
            num = stack.pop()
            cur = stack.pop() + int(num) * cur
        elif c.isdigit():
            d += c
        else:
            cur += c
    return cur

1541. Minimum Insertions to Balance a Parentheses String

平衡一个括号对，最少需要插入多少次，括号对为一个(对应2个)。原题

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

方法一：比赛时卡住了。这是Lee215的解法。想到了用栈和这种方式，但是没想好如何内部处理。

def minInsertions(self, s: str) -> int:
    ans = right = 0
    for c in s:
        if c == '(':
            if right&1 == 1:
                right -= 1
                ans += 1
            right += 2
        else:
            right -= 1
            if right < 0:
                right += 2
                ans += 1
    return ans + right

856. Score of Parentheses

括号的分数，根据规则计算括号的分数。()表示1分；AB表示A+B，(A)表示A*2。原题

Input: "()"
Output: 1
Input: "(())"
Output: 2
Input: "(()(()))"
Output: 6

方法一：首次AC的方法。

def scoreOfParentheses(self, S: str) -> int:
    stack = []
    for c in S:
        if c == '(':
            stack.append(c)
        else:
            if stack[-1] == '(':
                stack.pop()
                stack.append(1)
            else:
                v = 0
                while stack[-1] != '(':
                    v += stack.pop()
                stack.pop()
                stack.append(2 * v)
    return sum(stack)

方法二：Lee的方法太盖了，但是不知道咋想的，这个思路的过程我还是没想明白。

def scoreOfParentheses(self, S: str) -> int:
    stack, cur = [], 0
    for i in S:
        if i == '(':
            stack.append(cur)
            cur = 0
        else:
            cur += stack.pop() + max(cur, 1)
    return cur

方法三：O(1)space的方法，同样牛逼。

def scoreOfParentheses(self, S):
    res = l = 0
    for a, b in itertools.izip(S, S[1:]):
        if a + b == '()': res += 2 ** l
        l += 1 if a == '(' else -1
    return res

方法四：这个方法倒是没想到。

def scoreOfParentheses(self, S):
    return eval(S.replace(')(', ')+(').replace('()', '1').replace(')', ')*2'))

面试题 08.06. 汉诺塔问题

经典的汉诺塔问题，一个三个柱子，将盘子从A移动到C。

方法一：分治思想。

n = 1 时，直接把盘子从 A 移到 C；
n > 1 时，
先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
再将最大的盘子从 A 移到 C；
再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
    if not A: return
    n = len(A)

    def move(n, a, b, c):
        if n == 1:
            c.append(a.pop())
            return
        else:
            move(n-1, a, c, b)
            c.append(a.pop())
            move(n-1, b, a, c)

    move(n, A, B, C)

316. Remove Duplicate Letters

移除重复的字符，保证最后结果是字典序最小的。

Input: s = "bcabc"
Output: "abc"
Input: s = "cbacdcbc"
Output: "acdb"

方法一：使用stack来辅助判断。Lee的方法。

def removeDuplicateLetters(self, s: str) -> str:
    idx = {c: i for i, c in enumerate(s)}
    stack = []
    for i, c in enumerate(s):
        if c in stack: continue  # 这句别忘了 "cbacdcbc"
        while stack and stack[-1]>c and idx[stack[-1]]>i:
            stack.pop()
        stack.append(c)
    return ''.join(stack)

503. Next Greater Element II

下一个比当前元素大的元素，数组首位连接。原题

和1030题相似。方法一：首位连接，所以要遍历两次。

def nextGreaterElements(self, nums: List[int]) -> List[int]:
    ans, stack = [], []
    for num in nums * 2:
        while stack and stack[-1][1] < num:
            ans[stack.pop()[0]] = num
        stack.append((len(ans), num))
        ans.append(-1)
    return ans[:len(nums)]

方法二：实际并不需要保存数字。

def nextGreaterElements(self, nums: List[int]) -> List[int]:
    ans, stack = [-1]*len(nums), []
    for i in list(range(len(nums)))*2:
        while stack and nums[stack[-1]] < nums[i]:
            ans[stack.pop()] = nums[i]
        stack.append(i)
    return ans

946. Validate Stack Sequences

给定一个入栈和出栈的顺序，判断是否最后可以清空该栈。原题

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

def validateStackSequences(self, pushed: 'List[int]', popped: 'List[int]') -> 'bool':
    stack = []
    j = 0
    for num in pushed:
        stack.append(num)
        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return j == len(popped)

735. Asteroid Collision

行星碰撞，在一个横轴上有些数字表示行星的质量，正负表示方向，所有的行星以相同的速度运行，两个行星碰撞后质量小的会消失，相同则都消失，问最后剩余的行星。

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10.  The 5 and 10 never collide

方法一：很容易想到stack来解决，15分钟AC，需要注意内部也需要使用循环，因为有[10, 1, -5]这种情况，所以需要内循环不停地比较和碰撞。自认为比最高票答案写得简洁一些。

def asteroidCollision(self, asteroids: List[int]) -> List[int]:
    stack = []
    for a in asteroids:
        while stack and a<0 and stack[-1]>0:
            if stack[-1] > -a:
                break
            else:
                last = stack.pop()
                if last == -a:
                    break
        else:
            stack.append(a)
    return stack

456. 132 Pattern

是否有子序列是13,2的模式，即存在i<j<k，nums[i]<nums[j]<nums[k]

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

方法一：栈，挺难想的，看了答案才明白。third表示在当前值之后的小于当前数中最大的一个。

def find132pattern(self, nums: List[int]) -> bool:
    stack = []
    third = float('-inf')
    for num in reversed(nums):
        if num < third: return True
        while stack and stack[-1]<num:
            third = stack.pop()
        stack.append(num)
    return False

1673. Find the Most Competitive Subsequence

找到一个长度为k的最小的子序列。

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

方法一：竞赛时用了一个比较暴力+tricky方法过了5000个0的case。这题有些贪心的思想在里。

def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
    stack, N = [], len(nums)
    if sorted(nums) == nums:
        return nums[:k]
    for i, num in enumerate(nums):
        while stack and stack[-1] > num and len(stack)+N-i > k:
            stack.pop()
        if len(stack) < k:
            stack.append(num)
    return stack

84. Largest Rectangle in Histogram

柱形图里最大的矩形面积。

Input: [2,1,5,6,2,3]
Output: 10

方法一：单调栈，维护一个单调递增的栈，出栈时计算此高度的最大宽度，从而得出面积。一个难想的地方在于，这里每次出栈都更新一次结果。栈初始化为[-1]和尾部添0是一套操作，避免特殊情况的判断。

def largestRectangleArea(self, heights: List[int]) -> int:
    heights.append(0)
    stack, res = [-1], 0
    for i, h in enumerate(heights):
        while heights[stack[-1]] > h:
            hh = heights[stack.pop()]
            w = i - stack[-1] - 1
            res = max(res, hh * w)
        stack.append(i)
    return res

895. Maximum Frequency Stack

最大频率栈，每次返回频率最多的数。

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

方法一：这题的关键是要想明白数据冗余。每个频率上都保存一次数据。

class FreqStack:

    def __init__(self):
        self.cnt = Counter()
        self.freq = defaultdict(list)
        self.max_freq = 0

    def push(self, x: int) -> None:
        self.cnt[x] += 1
        self.max_freq = max(self.max_freq, self.cnt[x])
        self.freq[self.cnt[x]].append(x)

    def pop(self) -> int:
        d = self.freq[self.max_freq].pop()
        self.cnt[d] -= 1
        if not self.freq[self.max_freq]:
            self.max_freq -= 1
        return d

1776. Car Fleet II

车队，同853很像，区别在于求每辆车和前面车相撞的时间。

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

方法一：比赛时没有解出来，这是Lee的答案

def getCollisionTimes(self, A: List[List[int]]) -> List[float]:
    stack = []
    N = len(A)
    res = [-1] * N
    for i in range(N-1, -1, -1):
        p, s = A[i]
        # 不能是-1， 时间>则不能相撞
        while stack and (s<=A[stack[-1]][1] or (A[stack[-1]][0]-p) / (s-A[stack[-1]][1]) >= res[stack[-1]]>0):
            stack.pop()
        if stack:
            res[i] = (A[stack[-1]][0]-p) / (s-A[stack[-1]][1])
        stack.append(i)
    return res

150. Evaluate Reverse Polish Notation

计算逆波兰表达式。

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

方法一：提本身不难，Python有2个坑。一个是isdigit("-1")居然返回False。另一个是6//-13值为-1是向下取整。这和golang表现不一样。golang会输出0.

def evalRPN(self, tokens: List[str]) -> int:
    stack = []
    for token in tokens:
        if token[-1].isdigit():
            stack.append(int(token))
        elif token == "+":
            stack.append(stack.pop() + stack.pop())
        elif token == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif token == "*":
            stack.append(stack.pop() * stack.pop())
        else:
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a))
    return stack[-1]

224. Basic Calculator

实现一个计算带有括号的，只包含+-的算式。

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

方法一：栈，sign初始化2个1，是因为本身算式算一个+，如果是左括号开头又算一个+。这里我想到的差了一个1.

def calculate(self, s: str) -> int:
    sign = [1, 1]
    res = i = 0
    while i < len(s):
        c = s[i]
        if c.isdigit():
            start = i
            while i<len(s) and s[i].isdigit():
                i += 1
            res += sign.pop() * int(s[start:i])  
            continue
        if  c in "+(-":
            sign.append(sign[-1]*([1, -1][c=="-"]))
        elif c == ")":
            sign.pop()
        i += 1
    return res

1856. Maximum Subarray Min-Product

找到子数组，使得子数组的和与最小值的积最大。

Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.

方法一：比赛时思路对了，没有写出代码，其实枚举最小值就行，然后通过前缀和来找到，对于这个最小值，最侧第一个比它小的，和右侧第一个比它小的。使用单调递增栈来实现。

def maxSumMinProduct(self, nums: List[int]) -> int:
    MOD = 10 ** 9 + 7
    N = len(nums)
    left = [0] * N
    right = [N] * N
    stack = []
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]]>=num:
            right[stack[-1]] = i
            stack.pop()
        if stack:
            left[i] = stack[-1] + 1
        stack.append(i)
    pre_sum = list(accumulate([0]+nums))
    res = max((pre_sum[right[i]]-pre_sum[left[i]])*num for i, num in enumerate(nums))
    return res % MOD

1944. Number of Visible People in a Queue

右侧可以看见多少个人，可以看到比自己矮的。

Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.

方法一：比赛的时候想到单调栈，但是不知道怎么写，这是比较简单的题了。

def canSeePersonsCount(self, heights: List[int]) -> List[int]:
    N = len(heights)
    res = [0] * N
    stack = []
    for i in range(N-1, -1, -1):
        while stack:
            res[i] += 1
            if heights[i] > heights[stack[-1]]:
                stack.pop()
            else:
                break
        stack.append(i)
    return res