msg7086
2018-07-18 01:25:39 +08:00
第二题的解题思路：
首先是笨办法穷举，这个就不多说了。
接下来看优化方法。
首先我们知道最优解的大值在右边，小值在左边，那么小值可以覆盖大值左边的任意数据，大值可以覆盖小值右边的任意数据，而使得最优解不变。
比如说 [0, -5, -10, -5, 0, 5, 10, 5, 0] 的最优结果与 [0, -5, -10, -10, -10, -10, 10, 5, 0] 的结果是相同的，和 [0, -5, -10, 10, 10, 10, 10, 5, 0]的结果也是相同的。我这里把这种做法叫做极值覆盖。
那么解法就很简单了，生成两个极值覆盖数组，分别是小值向右覆盖，和大值向左覆盖：
min_array = [0, -5, -10, -10, -10, -10, -10, -10, -10]
max_arrray = [10, 10, 10, 10, 10, 10, 10, 5, 0]
然后对于每个下标，求最大差值即可。
代码如下：
input = [-1, 10, -8, 8, -10, 1]
min_array = input.dup
max_array = input.dup
1.upto(input.size-1) { |i| min_array[i] = [min_array[i-1], min_array[i]].min }
(input.size-1).downto(1) { |i| max_array[i-1] = [max_array[i-1], max_array[i]].max }
diff_array = input.size.times.map { |i| max_array[i] - min_array[i] }
max_diff = diff_array.max
p min_array
p max_array
p diff_array
puts max_diff
# [-1, -1, -8, -8, -10, -10]
# [10, 10, 8, 8, 1, 1]
# [11, 11, 16, 16, 11, 11]
# 16
时间复杂度三次线性遍历 O(n)，空间复杂度两次复制数组 O(n)。
接下来是继续优化空间复杂度。
我们看到大值覆盖是没有必要去计算的，直接用原始输入数据求值就行了，所以优化成：
min_array = input.dup
1.upto(input.size-1) { |i| min_array[i] = [min_array[i-1], min_array[i]].min }
diff_array = input.size.times.map { |i| input[i] - min_array[i] }
max_diff = diff_array.max
p min_array
p diff_array
puts max_diff
# [-1, -1, -8, -8, -10, -10]
# [0, 11, 0, 16, 0, 11]
# 16
时间复杂度两次线性遍历 O(n)，空间复杂度一次复制数组 O(n)。
再接下来我们发现小值覆盖也没有必要生成整个数组，而是只要记录至今为止的最小值即可，因为小值总是只会更小，后续计算不会涉及到历史值，因此优化成：
min = input.first
max_diff = 0
input.each do |n|
min = n if n < min
max_diff = n - min if n - min > max_diff
end
puts max_diff
# 16
时间复杂度一次线性遍历 O(n)，空间复杂度 O(1)。
同类型的 Trapping Rain Water 可以用第一种优化方法扫描覆盖极值来求解，有兴趣可以去挑战一下。