[代理镜像] data-structures/nextSmallerElement.cpp at main · SaadHusayn/data-structures · 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
75
76
77
78
79
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

// using recursion
// int getMin(vector<int> v, int i, int n){
//     if(i==v.size()) return n;

//     return getMin(v, i+1, min(n, v[i]));
// }

// void solve(vector<int> &v, vector<int> &result, int i){
//     if(i==v.size()){
//         return;
//     }

//     int mini = getMin(v, i+1, v[i]);

//     if(mini<v[i]) result[i] = mini;

//     solve(v, result, ++i);

// }

// vector<int> nextSmallerElement(vector<int> &v){
//     vector<int> result(v.size(), -1);
//     solve(v, result, 0);
//     return result;

// }

//stack implementation
void sortedInsert(stack<int> &st, int n){
    if(st.empty() || (!st.empty() && n<st.top())){
        st.push(n);
        return;
    }

    int element = st.top();
    st.pop();

    sortedInsert(st, n);

    st.push(element);
}
vector<int> nextSmallerElement(vector<int>& v){
    vector<int> result(v.size(), -1);

    stack<int> st;

    for(int i=(v.size()-1);i>=0;i--){

        if(!st.empty() && (st.top()<v[i])){
            result[i] = st.top();
            sortedInsert(st, v[i]);
        }
        else if(!st.empty()){
            st.push(v[i]);

        }else{
            st.push(v[i]);
        }

    }

    return result;
}


int main(){
    vector<int> v = {2, 1, 4, 3};

    vector<int> result = nextSmallerElement(v);

    for(auto i:result){
        cout << i << " ";
    }
}