作者:henrysong | 来源:互联网 | 2023-06-20 19:06
在数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。分析:最原始的方法是检查每一个数array[i],看是否左边的数都小于等于它,右边的数都大于等于它。这样做的话,要找出所
在数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。
分析:
最原始的方法是检查每一个数 array[i] ,看是否左边的数都小于等于它,右边的数都大于等于它。这样做的话,要找出所有这样的数,时间复杂度为O(N^2)。
其实可以有更简单的方法,我们使用额外数组,比如rightMin[],来帮我们记录原始数组array[i]右边(包括自己)的最小值。假如原始数组为: array[] = {7, 10, 2, 6, 19, 22, 32}, 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是说,7右边的最小值为2, 2右边的最小值也是2。
有了这样一个额外数组,当我们从头开始遍历原始数组时,我们保存一个当前最大值 max, 如果当前最大值刚好等于rightMin[i], 那么这个最大值一定满足条件。还是刚才的例子。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include