[codility]Array-closest-ascenders

http://codility.com/demo/take-sample-test/pi2012

又是一道单调栈的题目。首先这道题目n^2是最朴素的做法。继续优化，因为和顺序有关就不好排序。然后，看到可以分解成求左方向最值和右方向最值的问题。此时要变成O(n)就要么贪心，要么DP，要么单调栈，要么有更多规律未发现。

这里有这么一个特点，考虑求左方向最值，当先有4，再有5之后，那么之前的4就没有意义了。所以用单调栈。如果用函数，代码可以更简洁。

#include <stack>
vector<int> solution(const vector<int> &A) {
    // write your code in C++98
    int len = A.size();
    vector<int> R_left(len, 0);
    stack<int> left_stack;
    for (int i = 0; i < A.size(); i++) {
        while (!left_stack.empty() && A[left_stack.top()] <= A[i]) {
            left_stack.pop();
        }
        if (!left_stack.empty()) {
            R_left[i] = abs(left_stack.top() - i);
        }
        left_stack.push(i);
    }
    
    vector<int> R_right(len, 0);
    stack<int> right_stack;
    for (int i = A.size() - 1; i >= 0; i--) {
        while (!right_stack.empty() && A[right_stack.top()] <= A[i]) {
            right_stack.pop();
        }
        if (!right_stack.empty()) {
            R_right[i] = abs(right_stack.top() - i);
        }
        right_stack.push(i);
    }
    vector<int> R(len);
    for (int i = 0; i < len; i++) {
        if (R_right[i] == 0 && R_left[i] == 0) R[i] = 0;
        else if (R_right[i] == 0) R[i] = R_left[i];
        else if (R_left[i] == 0) R[i] = R_right[i];
        else R[i] = min(R_left[i], R_right[i]);
    }
    return R;
}