StartFragment#面试编程题# Given a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Could you find possible in O(n) algorithm. http://weibo.com/1915548291/zpuaLlfh5EndFragment

findijk.cpp

#include <cstdio>
#include <vector>
#include <assert.h>

using namespace std;
vector<int> getLeftMin(const vector<int> &vecAll)
{
    vector<int> vecMin;
    if (!vecAll.empty())
    {
        vecMin.reserve(vecAll.size());
        vecMin.push_back(vecAll[0]);
        for (size_t i = 1; i < vecAll.size(); i++)
        {
            vecMin.push_back(min(vecAll[i], vecMin.back()));
        }
    }
    return vecMin;
}

vector<int> getRightMax(const vector<int> &vecAll)
{
    vector<int> vecMax(vecAll.size());
    if (!vecMax.empty())
    {
        vecMax.back() = vecAll.back();
        for (size_t i = vecAll.size() - 1; i > 0; i--)
        {
            vecMax[i - 1] = max(vecMax[i], vecAll[i]);
        }
    }
    return vecMax;
}

bool findIJK(const vector<int> &vecAll, size_t &i, size_t &j, size_t &k)
{
    vector<int> vecLeftMin = getLeftMin(vecAll);
    vector<int> vecRightMax = getRightMax(vecAll);
    assert(vecLeftMin.size() == vecAll.size());
    assert(vecRightMax.size() == vecAll.size());
    for (j = 1; j < vecAll.size() - 1; j++)
    {
        if (vecLeftMin[j - 1] < vecAll[j] && vecAll[j] < vecRightMax[j + 1])
        {
            for (i = 0; i < j; i++)
            {
                if (vecAll[i] < vecAll[j])
                    break;
            }
            for (k = j + 1; k < vecAll.size(); k++)
            {
                if (vecAll[j] < vecAll[k])
                    break;
            }
            return true;
        }
    }
    return false;
}

int main()
{
    vector<int> vecAll;
    int a;
    while(scanf("%d", &a) == 1)
    {
        vecAll.push_back(a);
    }

    size_t i, j, k;
    if (findIJK(vecAll, i, j, k))
    {
        printf("%d %d %d\n", vecAll[i], vecAll[j], vecAll[k]);
    }
    else
    {
        printf("no\n");
    }

    return 0;
}