额外数组____O(n)寻找>=左侧所有数,<=右侧所有数

使用额外数组，比如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]， 那么这个最大值一定满足条件。还是刚才的例子。

 

参考来源：http://blog.jrj.com.cn/1832597331,5284403a.html 

//下列代码将上面方法颠倒了一下，输出也是逆向

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

void fun(int array[], int arraySize)
{
    int save[100];
    int i, min;

    for(i = 1, save[0] = array[0]; i < arraySize; i++)
    {
        if(array[i] > save[i-1])
            save[i] = array[i];
        else
            save[i] = save[i-1];            
    }//for(i=0;i<arraySize;i++)printf("%d ",save[i]);

    for(i = arraySize - 2, min = array[arraySize - 1]; i >= 1; i--)//去掉两端
    {
        if(min > array[i])
            min = array[i];
        if(min == save[i])
            printf("%d ", save[i]);
    }
}

int main()
{
    int a1[] = {7, 10, 2, 6, 19, 22, 32};
    
    fun(a1,7);
    return 0;
}