leetcode/456.cpp at master · Bright1992/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//
// Created by bright on 16-12-20.
//

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define INF456 0x7FFFFFFF

int findp(vector<int> &v, int t) {
    int s = v.size();
    int l = 0, r = s - 1, m = 0;
    while (l <= r) {
        m = (l + r) / 2;
        if (v[m] == t) {
            while (m >= 0 && v[m] == t) --m;
            return m + 1;
        }
        if (v[m] > t)
            r = m - 1;
        else
            l = m + 1;
    }
    if (v[m] > t) return m;
    else return m + 1;
}

bool find132pattern(vector<int> &nums) {
    int s = nums.size();
    if (s < 3) return false;
    vector<int> lmin(s, INF456), rmax(s, INF456);
    for (int i = 1; i < s; ++i) {
        if (nums[i - 1] < lmin[i - 1])
            lmin[i] = nums[i - 1];
        else
            lmin[i] = lmin[i - 1];
    }
    vector<int> rpart(1, 0);
    rpart[0] = nums[s - 1];
    for (int i = s - 2; i >= 0; --i) {
        int p = findp(rpart, nums[i]);
        if (p == 0)
            rpart.insert(rpart.begin(), nums[i]);
        else {
            rmax[i] = rpart[p - 1];
            rpart.insert(rpart.begin() + p, nums[i]);
        }
        if (rmax[i] < nums[i] && lmin[i] < nums[i] && rmax[i] > lmin[i])
            return true;
    }
    return false;
}

bool find132pattern_opt(vector<int> &nums){
    int s=nums.size();
    if(s<3) return false;
    vector<int> mn(nums.begin(),nums.end());
    for(int i=1;i<s;++i)    mn[i]=min(mn[i],mn[i-1]);
    vector<int> dp(s,-1);
    for(int i=1;i<s;++i){
        int j=i-1;
        while(j>=0&&nums[j]<=nums[i])
            j=dp[j];
        dp[i]=j;    //closest index larger than nums[i]
    }
    for(int i=2;i<s;++i){
        int j=dp[i];
        if(j>0&&nums[i]>mn[j-1])    return true;
    }
    return false;
}