一道经典题

给一个int数组，一个数K，K代表数组里相邻的K个数字

以K个数为单位遍历这个数组，每个单位里最小值为  minI,

求{min0, min1, min2......minN}里面的最大值

public int get(int[ ] arr, int k) {

}

例子：
input:    arr = {4,3,5,1}     k = 2
output:    3

分析：
分组： {4, 3}   {3, 5}   {5, 1}
min:         3       3         1

滑动窗口吗

Sliding windows

dengzx77 发表于 2020/03/15 00:01:23
滑动窗口吗

如果是用sliding window的话，是每次维护一个长度为k的子数组吗，这样在窗口移动的时候，如何更新子数组的最小值呢，比如[1,4,2,5,3],k=4。第一个长度为4的子数组最小值为1，第二个长度为4的子数组最小值2怎么提取出来呢，每次都用min函数或者小根堆来提取嘛？如果是这样感觉跟遍历没什么区别。还是有其他更好的方法？打扰了～

GCY_89757 发表于 2020/03/15 08:04:19
如果是用sliding window的话，是每次维护一个长度为k的子数组吗，这样在窗口移动的时候，如何更新子数组的最小值...

用两个指针L和R表示窗口的左端和右端，就不用一直维护一个额外的子数组了。在窗口移动的过程中，记录窗口内元素的最小值min。当R右移时，比较新元素和min的大小。当L右移时，如果原min移出，重新计算窗口的新min。这样应该会比遍历的O(nk)快些。

这个题可以看刷题网239, 最优解得用monotonic queue， sliding minimum 弄一个increasing的deque每次取head.

dengzx77 发表于 2020/03/15 09:33:19
用两个指针L和R表示窗口的左端和右端，就不用一直维护一个额外的子数组了。在窗口移动的过程中，记录窗口内元素的最小值min...

嗯嗯 对的！谢谢

https://www.geeksforgeeks.org/sl ... ubarrays-of-size-k/

看链接里的O(n)，是找出所有的k subarray max，跟你的题其实就一回事，max再去min就好了或者，每次取deque head的时候比较一下，就是max min了 （我觉得楼上说的就是这个）

（希望能有奖励）

dengzx77 发表于 2020/03/15 09:33:19
用两个指针L和R表示窗口的左端和右端，就不用一直维护一个额外的子数组了。在窗口移动的过程中，记录窗口内元素的最小值min...

可以用双端队列来做，这样就不用重新计算min了，跟利口二三就很像，你可以看一下～