leetcode(32)前缀和系列题目

303. 区域和检索 - 数组不可变

记录前i个元素的和，因此sum[left,right + 1]=pre[right + 1]-pre[left]

class NumArray:

    def __init__(self, nums: List[int]):
        self.pre_sum = [0]
        for i in range(len(nums)):
            self.pre_sum.append(self.pre_sum[i] + nums[i])

    def sumRange(self, left: int, right: int) -> int:
        return self.pre_sum[right + 1] - self.pre_sum[left]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

1856. 子数组最小乘积的最大值

前缀和+单调栈

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        pre_sum = [0]
        for i in range(len(nums)):
            pre_sum.append(nums[i] + pre_sum[i])
        res = 0
        nums = [-inf] + nums + [-inf]
        stack = []
        for r, n in enumerate(nums):
            while stack and nums[stack[-1]] > n:
                i = stack.pop()
                # print(nums[i])
                # print(nums[stack[-1]:r])
                cur = nums[i] * (pre_sum[r - 1] - pre_sum[stack[-1]])  # 注意r-1
                res = max(res, cur)
            stack.append(r)
        return res % (10 ** 9 + 7)