微软面试100题(93):数组里查找大于等于左侧所有数小于等于右侧所有数的数

在一个int 数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。

 

这个题目到手直观感受是相当于一轮快排。所以对原数组进行快排，完成后的序列和新序列如果值相等，那么说明该数满足条件。

文中的解答如下：

直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i 的最大的数和从后到i 的最小的数，一个解答：这需要两次遍历，然后再遍历一次原数组，将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。

 

该算法优化仅需不记录最小值数组，只记录当前最小值，并且符合条件直接输出即可

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX 10000

void getPiv(int *input, int size){
    if(input == NULL) return;
    int max[MAX] = {0};
    int i = 1;
    max[0] = input[0];
    for(;i<size;i++){
        max[i] = max[i-1];
        if(input[i]>max[i])
            max[i] = input[i];
    }
    int min = input[size-1];
    for(i=size-2;i>=0;i--){
        min = min>input[i] ? input[i] : min;
        if(input[i]>=max[i] && input[i]<=min)
            printf("%d \n", input[i]);
    }
}
int main(){
    int input[] = { 1,2,5,3,4};
    getPiv(input, sizeof(input)/sizeof(int));
}