推 sustainer123: 超難 我看解答 哭了 04/13 01:21
→ JIWP: 心焦u 04/13 01:23
推 SecondRun: 995 04/13 01:59
心焦U，出三小hrad
心焦U
42. Trapping Rain Water
有n個非負整數，每個整數的寬度是1
請問下雨後積水的面積
思路:
積水的條件是左右邊界比中間高
透過一個遞減的monotonic stack去存值
遞減monotonic stack的特性
當遇到當前值比stack top的值還大的時候
就把top pop出來，一直重複這個動作就可以得到一個遞減的排序
知道這個概念後就可以開始解題了
去遍尋heigt陣列，當height[i]>stack的top
就把stack top pop出來，這個pop出來的值會是底部，height[i]就是右邊界
再來去檢查stack裡面還有沒有值
1.沒有，不會有積水
2.有，左邊界為新的stack的top
且積水面積為(右邊界-左邊界-1)*(min(height[左邊界],height[右邊界])-height底部])
最後要把height[i] push進stack
重複這些動作就能得到答案了
golang code :
func trap(height []int) int {
stack := []int{}
ans := 0
for i := 0; i < len(height); i++ {
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
bottomidx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
leftbound := stack[len(stack)-1]
width := i - leftbound - 1
top := min(height[i], height[leftbound])
ans += (top - height[bottomidx]) * width
}
stack = append(stack, i)
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.143.104 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712942366.A.57E.html