Posted on

Stacks and Queues – StoneWall解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

題目解釋

在這個例子中,最後要建造的牆的寬度是 N = 9 米,高度在不同的位置上是不同的。牆的左端高度是 H[0] = 8,右端高度是 H[8] = 8。

這道題的目標是計算構建牆所需的最小石塊數,因此我們需要找到一種方法來計算構建牆所需的石塊數。我們可以使用一個堆疊來維護已經堆疊的石塊,然後從左到右遍歷數組,將石塊一層一層地堆疊起來。當當前高度高於前面高度時,應該添加一個新石塊。在堆疊石塊時,我們應該儘可能地重複使用現有的石塊,以減少新石塊的使用量。

你要建造一堵石牆,牆長 N 公尺,而牆的厚度是恆定的,但不同的位置高度不同。牆的高度由一個長度為 N 的正整數數組 H 指定。H[i] 表示牆的左端到右側 i 公尺處的高度。特別地,H[0] 是牆的左端高度,H[N-1] 是牆的右端高度。

石牆應由長方體石塊建造,所有面都是矩形。你的任務是計算構建牆所需的最小石塊數。

比方說,給定一個包含 N = 9 個整數的數組 H:

H[0] = 8 H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7 H[7] = 4 H[8] = 8

最終要的形狀會是不規則形,現在主要就是要計算有哪些是可以用更大的長方形去包含(把多個石塊用一個長方形合併起來)

對於給定的例子,以下是從左到右處理數組時的石塊堆疊狀態:

第 1 米處:添加一個高度為 8 的新石塊,堆疊中有 1 個石塊(堆疊中的石塊數為 1)。

第 2 米處:與前面的高度相同,不需要添加新的石塊,堆疊中有 1 個石塊(堆疊中的石塊數為 1)。

第 3 米處:當前高度比前面低,需要添加一個高度為 5 的新石塊,堆疊中有 2 個石塊(堆疊中的石塊數為 2)。

第 4 米處:當前高度比前面高,需要添加一個高度為 2 的新石塊,堆疊中有 3 個石塊(堆疊中的石塊數為 3)。

第 5 米處:當前高度比前面高,需要添加一個高度為 4 的新石塊,堆疊中有 4 個石塊(堆疊中的石塊數為 4)。

第 6 米處:當前高度比前面低,需要添加一個高度為 3 的新石塊,堆疊中有 5 個石塊(堆疊中的石塊數為 5)。

….以此類推

解題紀錄

function solution(H) {
    var stack = []
    var total = 0
    for(var i = 0;i<H.length;i++){
        if(stack.length == 0){
            stack.push(H[i])
            total++
        }else if(i > 0 && H[i-1] > H[i]){
            var height = H[i-1]
            while(stack.length > 0){
                height = height - stack.pop()
                if(height < H[i]) {
                    total++
                    stack.push(H[i]-height)
                    break
                }else if(height == H[i]){
                    break
                }
            }
        }else if(i > 0 && H[i-1] < H[i]){
            stack.push(H[i]-H[i-1])
            total++
        }else if(i ==  0 && H[i-1] < H[i]){
            stack.push(H[i])
            total++
        }
        //console.log(i,stack, total)
    }
    return total
}

https://app.codility.com/demo/results/training5QUJPS-FR6/