请教大家两道算法题，实在是想不出来了･ﾟ( ﾉд`ﾟ)

[angcz]

1.
给出一个已知长宽的二维数组 以斜着的 z 字型遍历该数组
比如：
{{1，2，3}，
{4，5，6}，
{7，8，9}}
输出为：
1 2 4 7 5 3 6 8 9
再比如：
{{1，2，3，4}，
{5，6，7，8}，
{9，10，11，12}}
输出为：
1 2 5 9 6 3 4 7 10 11 8 12

2.
给出一个已知长度的无序的一维数组 求出该数组任意两个元素值的最大差值 设这两个元素为 a,b 必须满足 a 的下标比 b 的下标小这一条件 时间复杂度要求 O(n) 空间复杂度要求 O(1)

在面试中遇到的两道题 太菜了 想了很久 最后只想出来了低效率方法或者笨办法 没有办法 只能请教大家了･ﾟ( ﾉд`ﾟ)

第二题表述有点问题 修改一下 就是给定 array[n] n 已知 求 array[i]-array[j]的最大值（ n>i>j>=0 ）

[mathzhaoliang]

第二个问题是否应该表述为：求出数组元素两两之差的最大值？

[mikeguan]

第二个问题如果我用两次冒泡求一个最大值和一个最小值 时间复杂度是 O(n)吗？

[mathzhaoliang]

第一个题目其实不难，你只要找出位于 (i, j) 处的元素在输出序列中的下标即可(用 i, j 表示)

[msg7086]

1.
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
1.upto(matrix.size + matrix.first.size - 1) do |l|
col = matrix.take(l).map(&:shift).compact
col.reverse! if l.odd?
p col
end

[1]
[2, 4]
[7, 5, 3]
[6, 8]
[9]

[xml123]

第二个的意思是“求 a_i-a_j 的最大值（ i>j ）”吧

[Xs0ul]

第二题先不管空间的，等于需要知道，给定每个下标，返回这个下标右边的最小值，这个从右到左扫一轮就行。然后再每个位置的值减它右边的最小值，这 n 个结果里面留一个最大的就行。

再优化空间复杂度，可以扫一个算一个差值，于是需要的变量是当前右侧最小值和最大的差值

[xml123]

5l 写错了一个地方，应该是 i<j
然后如果这个理解是正确的话，最大的差值肯定产生于某个极大值和它之后的某个极小值之差。读一边列表，维护 3 个数，过去出现的最大的数，最大数之后出现的最小数，以及最大的差值，应该就能满足要求了。（不过如果数组是递增的话好像还是会有 bug，这种情况额外处理一下吧）

[xwyam]

第一题 python 实现
ZGVmIGdlbihtLCBuKToKICAgIGZvciBzIGluIHJhbmdlKG0gKyBuIC0gMSk6CiAgICAgICAgaSwg
aiA9IChzLCAwKSBpZiBzIDwgbSBlbHNlIChtIC0gMSwgcyAtIG0gKyAxKQogICAgICAgIHgsIHkg
ID0gKDAsIHMpIGlmIHMgPCBuIGVsc2UgKHMgLSBuICsgMSwgbiAtIDEpCiAgICAgICAgd2hpbGUg
aSA+PSB4IGFuZCBqIDw9IHk6CiAgICAgICAgICAgIHlpZWxkIChpLCBqKQogICAgICAgICAgICBp
LCBqID0gaSAtIDEsIGogKyAx

[msg7086]

第二题相当于是 Trapping Rain Water 的一个特例，最直观的做法是新开两个数组存覆盖结果，然后再相减。
空间复杂度 O(1)不知道能不能实现，回头我想一下然后贴代码上来。

[xwyam]

第二题一个简单的思路，扫描两趟，第一趟找出最大值 A 和最小值 V，第二趟找出最小值之后的最大值 M 和最大值之前的最小值 W，A-W 和 M-V 中较大数即是所求

[xwyam]

@mikeguan 是 O(n)

[angcz]

@mathzhaoliang 是的 你的理解是对的 我表述得有些问题

[angcz]

@xml123 呃 5L 的理解是对的 就是给定 array[n] 求 array[i]-array[j]的最大值（ i > j ）

[xml123]

@angcz 那把 7l 的方法反过来就行了（大和小换一下，或者逆序遍历数组）

[msg7086]

#10 @xwyam [-1, 10, -8, 8, -10, 1]

[ihainan]

第一题，我想到的笨方法是，因为对角线行号列号之和相同，所以可以外层循环穷举所有可能的和，内层循环穷举在这个和之下所有可能的行号。

第二题，从左往右，记录当前左侧最小值，计算当前值和最小值的差值，再记录当前位置的最大差值。注意数组为空和只有一个元素的情况。

[timle1029]

第一题是 leetcode 原题 https://leetcode.com/problems/diagonal-traverse/description/

第二题没有这么复杂吧，从后往前扫，记录一个 maxValue, 遇到更大的就替换，遇到比这个 Value 小的就计算比较结果
public int maxDifference(int[] nums) {
int len = nums.length;
int maxValue = nums[len - 1];
int res = 0;
for (int i = len - 2; i >= 0; i--) {
if (nums[i] < maxValue) {
res = Math.max(maxValue - nums[i], res);
} else {
maxValue = Math.max(mavValue, nums[i]);
}
}
return res;
}

[kj]

第二题，两个指针，一个从左往右找更小的，一个从右往左找更大的

[Andiry]

LC498
LC121

[msg7086]

第二题的解题思路：

首先是笨办法穷举，这个就不多说了。

接下来看优化方法。
首先我们知道最优解的大值在右边，小值在左边，那么小值可以覆盖大值左边的任意数据，大值可以覆盖小值右边的任意数据，而使得最优解不变。

比如说 [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 可以用第一种优化方法扫描覆盖极值来求解，有兴趣可以去挑战一下。

[xwyam]

@msg7086。。。之前想法好像确实不行。。。

[yidinghe]

第二题怎么看都是找数组的最大最小值啊。

[ihainan]

顺手把两题 A 了： https://gist.github.com/ihainan/1d73a472243b4e954e589518c3d34287