求k长度子数组最小值的最大值的算法实现原理疑问

问题1：array2的作用是什么 #

array2是从右往左遍历原数组，以每k个元素为一个分块，存储每个位置到它所在分块右边界的区间最小值，和从左往右计算分块左前缀最小值的array1是互补的关系。

拿你给出的示例数组[2,5,4,6,8]、k=3来举例，原数组按每3个为一块拆分后是[2,5,4]、[6,8]，计算得到的array2结果是[2,4,4,6,8]，比如array2[1]的值是4，代表从索引1到它所在第一块的右边界索引2的区间[5,4]的最小值是4。

问题2：minimaList.add(Math.min(array1[i + k - 1], array2[i]))这段逻辑是如何计算得到k窗口子数组的最小值的 #

任意一个长度为k的滑动窗口，起始位置是i，结束位置是i+k-1，它最多只会跨2个连续的k长度分块：

• 窗口的左半部分，从i到它所在分块的右边界，这部分的最小值刚好存在array2[i]里（因为array2存的就是i到所在块右边界的最小值）
• 窗口的右半部分，从它所在分块的左边界到i+k-1，这部分的最小值刚好存在array1[i+k-1]里（因为array1存的就是i+k-1到所在块左边界的最小值）

整个窗口的最小值就是这两部分最小值的较小值，所以直接取Math.min(array1[i + k - 1], array2[i])就能得到当前窗口的最小值。

还是用你示例里第二个窗口[5,4,6]举例，i=1，结束位置是3：

• array2[1]是窗口左半部分[5,4]的最小值4
• array1[3]是窗口右半部分[6]的最小值6
• 两者取min得到4，刚好是整个窗口的最小值。

问题3：如果array1已经存储了所有k窗口的最小值，为什么不能直接返回array1中的最大值作为结果 #

首先你的前提就不成立：array1根本没有存储所有k窗口的最小值，它存的只是每个分块内部的左前缀最小值，只有每个分块的右边界位置的array1值，才对应刚好和分块重合的那个窗口的最小值，其他位置的array1值都不是完整k长度窗口的最小值。

还是用示例计算结果验证：示例的array1数组是[2,2,2,6,6]，里面根本没有第二个、第三个窗口的最小值4，你直接取array1的最大值是6，和正确结果4完全不符，所以不可能直接用array1的最大值当结果。

内容的提问来源于stack exchange，提问作者Learner