贡献法

828. 统计子串中的唯一字符 - 力扣（LeetCode）

贡献法 一个字符 能贡献1 代表他在这个子数组里 是唯一的 那就求这样的子数组有多少个 那就在前后找 他上一个和下一个相同元素 这中间的所有数的子数组个数 就是贡献度

预处理这个字符的前后的相同的字符的位置 然后再用乘法原理算出来相同子数组的个数 注意这里的子数组是类子串而不是类子序列

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        res = 0
        m = {}
        l = [0] * n
        r = [0] * n
        for i in range(n):
            x = s[i]
            l[i] = m.get(x, -1)
            m[x] = i
        m.clear()
        for i in range(n - 1, -1, -1):
            x = s[i]
            r[i] = m.get(x, n)
            m[x] = i
        
        res = sum((i - a) * (b - i) for i, (a, b) in enumerate(zip(l, r)))
        return res

907. 子数组的最小值之和 - 力扣（LeetCode）

贡献法 求每个数能为答案贡献多少度 那就要看 他在几个子数组里是最小值 那就分别去找 这个数两边 是不是有比他更小的数

一个数能提供的度数 就是a * （i - l）*（r - i） 其中l， r 为他左右比他更小的数的下标 没有就是-1 或 n

要找这样的数 每个数的前后比他更小的 就用单调栈

从左往右 放入数 一旦遇到比栈顶小的 就pop 直到比栈顶大或栈为空 放入元素 更新下标

此时 把栈顶踢出的（i）是栈顶的右边界 而最终停止pop后 如果栈顶有元素（说明是比i小的）就是i的左边界

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        mod = 10 ** 9 + 7
        n = len(arr)
        left, right = [-1] * n, [n] * n
        st = []
        i = 0
        for i, x in enumerate(arr):
            while st and arr[st[-1]] <= x:
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(x)
        res = sum(a * (i - l) * (r - i) for i, (l, r) in enumerate(zip(left, right)))
        return res

2477. 到达首都的最少油耗 - 力扣（LeetCode）

计算每条边的贡献 到首都的人数是固定的 每个人要走的边也是固定的 因此可以用贡献法直接计算出每条边会有多少人经过 然后再把这个贡献 // 车载数 就可以得到这条边上要消耗的油量 然后把所有边加起来就行

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
    g = defaultdict(list)
    for a, b in roads:
        g[a].append(b)
        g[b].append(a)
    
    ans = 0
    # 令dfs返回这条路的人数
    def dfs(x, fa):
        # 每条路至少有端点这一个人走
        ret = 1
        for y in g[x]:
            if y != fa:
                nonlocal ans
                t = dfs(y, x)
                ans += (t - 1) // seats + 1
                # 现在ret 就是这个点到终点的人数 （注意一个点可通向多个点 有多个终点 这些终点是不算在这个ret里的 而是算在fa的ret里）
            	ret += t
        return ret
	dfs(0, -1)
    return ans
                

979. 在二叉树中分配硬币 - 力扣（LeetCode）

类似于贡献法 算出棵子树的硬币总数 和结点数 就可以算出 有多少硬币要移出这棵子树 然后就可以算出 有多少硬币要移出这个子树的边

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        ans = 0
        # 返回硬币数和结点数
        def dfs(root:TreeNode) -> (int, int):
            if root is None:
                return (0, 0)
            l_c, l_n = dfs(root.left)
            r_c, r_n = dfs(root.right)
          	coin = l_c + r_c + root.val
            node = l_n + r_n + 1
            nonlocal ans
            ans += abs(coin - node)
            return (coin, node)
        dfs(root)
        return