Monotonic Stack

Monotonic stack 是一種 stack，其中裡面的元素的值必須是遞增或是遞減。

Monotonic Stack

以下的演算法會產生遞增的 monotonic stack。每當要 push 一個值 x 進去 stack 之前，它會先檢查 stack 最上面的值是否大於 x，如果是就 pop 最上面的值。它就這樣反覆地檢查值到最上面的值小於 x，然後再 push x 進去 stack。最後，產生出來的 stack 是遞增的。

Algorithm IncreasingMonotonicStack(arr) {
    stack := Stack();
    for i in arr {
        while stack.isNotEmpty && stack.peek() > i {
            stack.pop();
        }
        stack.push(i);
    }
    return stack;
}

以下的演算法則是會產生遞減的 monotonic stack。

Algorithm DecreasingMonotonicStack(arr) {
    stack := Stack();
    for i in arr {
        while stack.isNotEmpty && stack.peek() < i {
            stack.pop();
        }
        stack.push(i);
    }
    return stack;
}

範例