https://leetcode.com/problems/sum-of-total-strength-of-wizards/
好题！算是对前缀和以及单调栈的极致运用了，解法需要反复揣摩才能看得懂。

个人解答

参考：https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/JavaC%2B%2BPython-One-Pass-Solution
以及其中关于acc2相减的comment

  1. class Solution:
  2.     def totalStrength(self, a: List[int]) -> int:
  3.         MOD = 10**9 + 7
  4.         n = len(a)
  5.         left_small = [-1] * n
  6.         right_small_equal = [n] * n
  8.         stk = []
  9.         for i in range(n):
  10.             while stk and a[stk[-1]] >= a[i]:
  11.                 right_small_equal[stk.pop()] = i
  12.             stk.append(i)
  14.         stk = []
  15.         for i in range(n - 1, -1, -1):
  16.             while stk and a[stk[-1]] > a[i]:
  17.                 left_small[stk.pop()] = i
  18.             stk.append(i)
  20.         acc2 = list(accumulate(accumulate(a), initial=0))
  22.         res = 0
  23.         for i in range(n):
  24.             l, r = left_small[i], right_small_equal[i]
  25.             ln, rn = i - l, r - i
  26.             lacc2, racc2 = acc2[i] - acc2[max(l, 0)], acc2[r] - acc2[i]
  27.             res += a[i] * (racc2 * ln - lacc2 * rn) % MOD
  29.         return res % MOD

题目解析

有很多值得关注的点。

整体思路

比较容易想到，从找到所有的子数组，转化为，对每一个元素分析，包含该元素的子数组，这样可以做到不重不漏。
整体解法：对每一个元素，找出以其为最小值的子数组，从而进一步按照题目要求计算乘积之和。
所以涉及两点：

  1. 以其为最小值的子数组，这个可以左右延伸，直至找到比它更小的。
  2. 题目要求的乘积之和计算，这个也有巧妙的方式。

    单调栈的应用

    参见题解，确实精妙。
    要找出每个元素某一侧出现的第一个比它小的元素位置，单调栈可以很好地解决。
    不能只盯着单调栈当前处理地值和栈中已有地值，往往那些要pop出去地，才是自己关心的，这个思路值得借鉴。

    计算乘积之和

    这个就更巧妙了，参照：https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/JavaC++Python-One-Pass-Solution/1401223
    经过一番转化，可以变成前缀和的前缀和之间的运算，很是巧妙。具体的参考题解。

    边界值考虑

    上边两点都需要考虑边界值。
    因为涉及相等的值，就要防止相同值被算两次，这个可以约定是左开右闭还是左闭右开，像题解中是左闭右开，既左边的相等的保留，右边的相等的不保留，因此左边的终点是比当前值更小的，右边的终点是小于等于当前值。
    前缀也要约定好对应的acc[i]的范围，是[0,i]还是[0,i)，还有在前边加入一个默认的0的时候，又要怎么考虑。
    上边链接中关于acc2相减的解答其实就没有讲清楚这一点，这个还是要用实际的case来看。目前没有找到什么best practice的东西。
    这种题目确实需要反复揣摩练习，才能又快又准确的写出来。