Monotonic Stack

[caipengbo]

单调栈框架 以单调递增栈为例： Next Less Element Previous Less Element

for (int i = 0; i < n; i++) {
    right[i] = n-i;  // 某些元素不能进到pop循环，所以赋初值
    while (!stack.empty() && A[stack.peek()] > A[i]) {
        int peek = stack.pop();
        right[peek] = i - peek;  //  pop时操作  Next Less Element
    }
    // 栈为空时需要特殊赋值
    left[i] = (stack.empty() ? i+1 : i - stack.peek());   // push时操作，Previous Less Element
    stack.push(i);
}

[caipengbo]

递减栈 和 递增栈相反，求Next Great Element 和 Previous Great Element