Skip to content

Contribution Method

Table of Contents

907. Sum of Subarray Minimums

2104. Sum of Subarray Ranges

1856. Maximum Subarray Min-Product

2818. Apply Operations to Maximize Score

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, stack, greedy, sorting, monotonic stack, number theory

2281. Sum of Total Strength of Wizards

2281. Sum of Total Strength of Wizards - Python Solution
from itertools import accumulate
from typing import List


# Monotonic Stack
def totalStrength(strength: List[int]) -> int:
    n = len(strength)
    left = [-1 for _ in range(n)]
    right = [n for _ in range(n)]
    stack = []

    for i, v in enumerate(strength):
        while stack and strength[stack[-1]] >= v:
            right[stack.pop()] = i
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    prefix_sum = list(accumulate(accumulate(strength, initial=0), initial=0))

    ans = 0
    for i, v in enumerate(strength):
        l, r = left[i] + 1, right[i] - 1
        tot = (i - l + 1) * (prefix_sum[r + 2] - prefix_sum[i + 1]) - (
            r - i + 1
        ) * (prefix_sum[i + 1] - prefix_sum[l])
        ans += v * tot

    return ans % (10**9 + 7)


strength = [1, 3, 1, 2]
print(totalStrength(strength))  # 44

3359. Find Sorted Submatrices With Maximum Element at Most K

2334. Subarray With Elements Greater Than Varying Threshold

Comments