判断是否存在i<j<k，a[i]<a[k]<a[j]

暴力做法：

时间复杂度



O

(

N

3

)

O(N^3)






O


(



N










3









)

// 暴力解法O(N^3)
int baoli(int *a, int right){
    for(int i = 0; i < right; i++){
        for(int k = 0; k < right; k++){
            for(int j = 0; j < right; j++){
                if (i < j && j < k && a[i] < a[k] && a[k] < a[j]){
                    cout << "i:" << i << " j:" << j << " k:" << k << endl;
                    return 1;
                }
            }
        }
    }
    return 0;
}

算法

时间复杂度：



O

(

N

)

O(N)






O


(


N


)

维护

一个前缀最小值下标数组minid

一个后缀最大值下标数组maxid

再枚举j

a[minid[j-1]]<a[j]<a[maxid[j+1]]

即可

代码如下：

#include <iostream>
#include <cstring>

using namespace std;

// 题目：一个数组a，判断是否存在i<j<k, a[i]<a[k]<a[j]

// 暴力解法O(N^3)
int baoli(int *a, int right){
    for(int i = 0; i < right; i++){
        for(int k = 0; k < right; k++){
            for(int j = 0; j < right; j++){
                if (i < j && j < k && a[i] < a[k] && a[k] < a[j]){
                    cout << "i:" << i << " j:" << j << " k:" << k << endl;
                    return 1;
                }
            }
        }
    }
    return 0;
}

// 算法O(N)
int judge(int *a, int right){
    a[0] = INT_MAX;
    int minid[10];
    int maxid[10];
    memset(minid, 0, sizeof(minid));
    memset(maxid, 0, sizeof(maxid));
    // 前缀最小值下标数组
    for(int i = 1; i < 10; i++){
        if(a[i] < a[minid[i - 1]]){
            minid[i] = i;
        }else{
            minid[i] = i - 1;
        }
    }
    // 后缀最大值下标数组
    maxid[9] = 9;
    for(int i = 8; i > 0; i--){
        if(a[i] > a[maxid[i + 1]]){
            maxid[i] = i;
        }else{
            maxid[i] = i + 1;
        }
    }
    for (int i = 0; i < 10; i++){
        printf("%d ", minid[i]);
    }
    cout << endl;
    for (int i = 0; i < 10; i++){
        printf("%d ", maxid[i]);
    }
    cout << endl;
    // 找k，存在则返回
    for(int j = 1; j < 10; j++){
        if(a[minid[j - 1]] < a[maxid[j + 1]] && a[maxid[j + 1]] < a[j]){
            cout << "j:" << j << "  minid[j-1]:" << minid[j - 1] << "  maxid[j+1]:" << maxid[j + 1] << endl;
            cout << "a[maxid[j + 1]]:" << a[maxid[j + 1]] << " a[j]:" << a[j] << endl;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int a[10] = {0, 1, 8, 5, 4, 3, 6, 7, 2, 9};
    if (1 == judge(a, 9)){
        printf("存在\n");
    }else{
        cout << "不存在\n";
    }
    return 0;
}