#include <stack>
#include <iostream>
#include <vector>
#include <random>
#include <time.h>
using std::cout;
using std::stack;
using std::vector;
using std::default_random_engine;
using std::uniform_int_distribution;
void GenerateRandomSeqence(int size, vector<int> &out)
{
default_random_engine e;
uniform_int_distribution<int> id(0, 20);
e.seed(time(nullptr));
cout << time(nullptr) << "\n";
for (int i = 0; i < size; i++)
{
out.push_back(id(e));
}
}
bool CanGenerateStack(vector<int> &sequence)
{
int top = sequence.size() - 1;
for (int i = top; i > 1; i--)
{
int minIndex = i;
int curHead = sequence[i];
for (int j = top - 1; j >= 0; j--)
{
if (sequence[j] >= curHead)
{
continue;
}
if (sequence[j] > sequence[minIndex])
{
cout << "a: " << sequence[minIndex] << ", b: " << sequence[j] << ", c: " << curHead << "\n";
return false;
}
else
{
minIndex = j;
}
}
}
return true;
}
void PrintVector(const vector<int> &sequence)
{
for (auto &&v : sequence)
{
cout << v << " ";
}
cout << "\n";
}
int main()
{
const int SEQUENCE_SIZE = 5;
vector<int> sequence(SEQUENCE_SIZE);
GenerateRandomSeqence(SEQUENCE_SIZE, sequence);
PrintVector(sequence);
bool ret = CanGenerateStack(sequence);
cout << (ret ? "CanGenerate" : "CanNotGenerate") << "\n";
return 0;
}
run 10 times !
=================== 1 ==================
1641409646
5 5 8 14 11
CanGenerate
=================== 2 ==================
1641409647
5 8 3 2 1
CanGenerate
=================== 3 ==================
1641409648
5 11 19 12 13
CanGenerate
=================== 4 ==================
1641409649
5 13 14 1 3
a: 1, b: 13, c: 14
CanNotGenerate
=================== 5 ==================
1641409650
5 16 9 10 14
CanGenerate
=================== 6 ==================
1641409651
5 19 4 20 4
a: 4, b: 19, c: 20
CanNotGenerate
=================== 7 ==================
1641409652
5 1 20 9 15
a: 1, b: 5, c: 15
CanNotGenerate
=================== 8 ==================
1641409653
5 4 14 18 6
a: 4, b: 5, c: 6
CanNotGenerate
=================== 9 ==================
1641409654
5 6 9 7 17
a: 7, b: 9, c: 17
CanNotGenerate
=================== 10 ==================
1641409655
5 9 4 16 7
a: 4, b: 5, c: 7
CanNotGenerate