https://codility.com/programmers/challenges/upsilon2012
求笛卡尔树的高度，可以用单调栈来做。
维持一个单调递减的栈，每次进栈的时候记录下它之后有多少元素，就是以它为根的子树的高度。出栈的时候再更新一次供新进栈者使用。
int solution(vector<int> &A) {
A.push_back(1000000001); // an element larger than any one in A
int size = A.size();
vector<int> elem_stack;
vector<int> ht_stack;
int tailHt = 0;
for (int i = 0; i < size; i++) {
bool done = false;
while (not done) {
if (elem_stack.size() == 0
|| elem_stack.back() > A[i]) {
elem_stack.push_back(A[i]);
ht_stack.push_back(tailHt);
tailHt = 0;
done = true;
} else { // pop up
elem_stack.pop_back();
tailHt = max(ht_stack.back(), tailHt) + 1;
ht_stack.pop_back();
}
}
}
return ht_stack.back();
}