https://codility.com/programmers/challenges/upsilon2012

求笛卡尔树的高度，可以用单调栈来做。

维持一个单调递减的栈，每次进栈的时候记录下它之后有多少元素，就是以它为根的子树的高度。出栈的时候再更新一次供新进栈者使用。

int solution(vector
     
       &A) {    A.push_back(1000000001); // an element larger than any one in A    int size = A.size();    vector
      
        elem_stack;    vector
       
         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();}