題目內容
題目頁面: 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/
