907. Sum of Subarray Minimums - 简书
实际上是要求
res = sum(A[i] * f(i))，其中f(i)是子数组的数量，A[i]是最小值。
为了得到f(i)，我们要得到
-
left[i]，能在A[i]左侧取得的最长宽度，使得在这个范围内A[i]是最小值,且都大于A[i] -
right[i], 能在A[i]右侧取得的最长宽度，使得在这个范围内A[i]是最小值，且都大于等于A[i]
然后，
-
A[i]左侧有left[i] + 1种连续子数组的取法 -
A[i]右侧有right[i] + 1种连续子数组的取法
最后根据f(i) = (left[i] + 1) * (right[i] + 1)即可求得f(i)
所以这个问题在于求left[i]和right[i]
举例，对于[3,1,2,4]：
left + 1 = [1,2,1,1]
right + 1 = [1,3,2,1]
f = [1,6,2,1]
res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17
那么，解释一下为什么left[i]要取大于A[i]，而right[i]只需要取大于等于A[i]：
他是为了解决数组中有相等的数的情况。
假设有数组...a1...a2...a3... ...an...其中，a1=a2=a3=...=an，那么这个连续数组的各种组合中，起点可以起自...a1, ...a2, ...a3，直到...an，而终点则可以尽可能地往右边取。
所以在i=a1处，left[i]最多取到a1，而在i=a2处，left[i]最少也取到a1+1。如此类推，起点可以从...a1...a2一直取到an，而终点可以从起点一直取到最右侧（只要大于等于起点的值），如此可以把全部的连续子数组的情况覆盖。
算法
那么怎么求得left[i]和right[i]呢？我们可以看以下两个同类型的问题的讨论:
答案主要有两种做法，一种是用栈，一种是用数组。
解决方案1：栈
[C++/Java/Python] O(1)
就是用increasing stack来解决问题。
解决方案2：数组
5ms O(n) Java solution explained (beats 96%)
本来遍历要一个一个遍历的，像这样：
for (int i = 1; i < height.length; i++) { int p = i - 1; while (p >= 0 && height[p] >= height[i]) { p--; } lessFromLeft[i] = p; } 但我们可以改良它，在往前遍历时不一个一个地遍历，而是利用之前的计算结果，直接"跳"过多个元素:
while (p >= 0 && height[p] >= height[i]) { p = lessFromLeft[p]; }Read full article from 907. Sum of Subarray Minimums - 简书
No comments:
Post a Comment