题解 | #132序列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return bool布尔型
 */
#include <stdio.h>
bool find132Subseq(int* nums, int numsLen ) {
    // write code here
    if(numsLen<3){
        return false;
    }
    int* up = (int*)malloc(numsLen * sizeof(int));
    int* down = (int*)malloc(numsLen * sizeof(int));
    int min=nums[0],max=nums[0],i,j,utop=0,dtop=0;
    up[utop]=0;
    down[dtop]=0;
    printf("min:%d max:%d\n",min,max);
    for(i=1;i<numsLen;i++){
        if(nums[i]<=min){
            down[++dtop]=i;
            printf("in1 当前值:%d max:%d min:%d up栈顶:%d down栈顶:%d\n",nums[i],max,min,nums[up[utop]],nums[down[dtop]]);
        }else if(nums[i]>max){
            min=nums[down[dtop]];
            up[++utop]=i;
            max=nums[up[utop]];
            printf("in2 当前值:%d max:%d min:%d up栈顶:%d down栈顶:%d\n",nums[i],max,min,nums[up[utop]],nums[down[dtop]]);
        }else if(nums[i]==max){
            min=nums[down[dtop]];
            printf("in3 当前值:%d max:%d min:%d up栈顶:%d down栈顶:%d\n",nums[i],max,min,nums[up[utop]],nums[down[dtop]]);
        }else if(nums[i]<max){
            printf("in4 当前值:%d max:%d min:%d up栈顶:%d down栈顶:%d\n",nums[i],max,min,nums[up[utop]],nums[down[dtop]]);
            free(up);
            free(down);
            return true;
        }
    }
    free(up);
    free(down);
    return false;
}

1.使用了两个栈（up&down），初始值都为nums[0]，分别存储逐渐增大的值和逐渐减小的值，即存储可能的“1”和“3”；

2.使用min和max来存储实际使用的“1”和“3”（max一直是up栈顶，min则是down栈中索引比max小的元素，当max更新时可以同时更新min为当前down栈顶）；

3.当nums[i]<min时，压入down栈作为可能的“1”，但不能实际使用；

当nums[i]>max时，压入up栈，更新max和min；

当nums[i]=max时，更新min；

当nums[i]<max时，表示当前值符合“2”的条件，返回true；

运行举例：