Monotonic Stack

Photo by Chris Czermak on Unsplash
Photo by Chris Czermak on Unsplash
Monotonic stack 是一種 stack,其中裡面的元素的值必須是遞增或是遞減。

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

Table of Contents
  1. Monotonic Stack
  2. 範例

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;
}

範例

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You May Also Like
Photo by Léonard Cotte on Unsplash
Read More

Depth First Search (DFS)

深度優先搜尋(DFS)演算法是一種圖形搜尋演算法。從給定的一個點開始,它會先探索該點的一個相鄰點。再來,探索該相鄰點的一個相鄰點。這樣子一直探索下去,直到某的點沒有相鄰點時,它就會退回到上一個點,並探索該點的下一個相鄰點。它會一直這樣地探索下去,直到找到結果,或是探索完所有的點。
Read More
Photo by Pedro Lastra on Unsplash
Read More

Breadth First Search (BFS)

廣度優先搜尋(BFS)演算法是一種圖形搜尋演算法。從給定的一個點開始,它會先探索該點所有的相鄰點。再來,依序探索這些相鄰點的相鄰點。這樣子一層一層地探索下去,直到找到結果,或是探索完所有的點。
Read More
Photo by Simon Hermans on Unsplash
Read More

Priority Queue & Heap

Priority queue 是一個很好用的 data structure。它可以在常數時間內提供最大或最小值。在了解它之前,我們要先了解另一個 data structure 叫 heap。因為 priority queue 常常會用 heap 來實作。
Read More
Photo by Anthony DELANOIX on Unsplash
Read More

Union Find

Union Find data structure 又稱 disjoint set data structure。它是一個資料結構,用來儲存一堆 disjoint set。它提供兩個操作,一個是用來合併兩個 sets,另一個是用來尋找給定元素的 set。
Read More
Photo by Folco Masi on Unsplash
Read More

Binary Search Tree

二元搜尋樹(Binary search tree, BST)是一種二元樹(binary tree)。它提供了一些有用操作,包含 search、insert、delete、minimum、maximum、successor 和 predecessor。
Read More