群里看到一个heapq 没看到为啥WA了？ .立个flag明天读

import heapq
class Solution:
    def minimumOperations(self, leaves: str) -> int:
#(即优先队列priority queue)
        n = len(leaves)
        R, Y = [0] * n, [0] * n
        for i in range(n):
            R[i] = R[i - 1] + 1 if leaves[i] == 'r' else R[i - 1]
            Y[i] = Y[i - 1] + 1 if leaves[i] == 'y' else Y[i - 1]
        heap = []
        for i in range(n):
            heapq.heappush(heap, [-(Y[i] - R[i]), i])
        res = float('inf')
        for j in range(n - 2, 0, -1):
            while heap and heap[-1][1] >= j:
                heap.pop()
            res = min(res, Y[n - 1] + R[j]- Y[j]-heap[-1][0])
        return res

题目描述

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。

变成「红、黄、红」即可。Q:请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

样例

leaves = "rrryyyrryyyrr"
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"

以下是另外一个AC代码

def minimumOperations(self, leaves: str) -> int:
        # 简化的 dp
        # r 代表当前位置是 r* 型的可能性
        # ry 代表当前位置是 r*y* 型的可能性
        # ryr 分别代表当前位置是 r*y*r* 型的可能性
        r, ry, ryr = int(leaves[0] == 'y'), float('inf'), float('inf')
        for i in range(1, len(leaves)):
            x = int(leaves[i] == 'y')
            r, ry, ryr = r+x, min(r, ry)+(1-x), min(ry, ryr)+x
        return ryr