python c++用monotonic stack解 Leetcode難題42 trapping rain water並附pyplot繪直方圖解說

Python c++用monotonic stack解 Leetcode難題42 trapping rain water並附pyplot繪直方圖解說

想法是使用索引 m 的單調堆疊來找到右牆height[r]和左牆height [l]；計算此區域高於底部 height[m]的水量應為min(height[r]-height[m], height[l]-height[m])*(r-l-1) 

---

python c++ uses monotonic stack to solve Leetcode problem 42 trapping rain water with explanation of histogram drawing with pyplot

The idea is using monotonic stack for index m to find the right wall height[r] & left wall height[l]; this region should has water amount above the bottom height[m] of min(height[r]-height[m], height[l]-height[m])*(r-l-1)

[codes on Leetcode]https://leetcode.com/problems/trapping-rain-water/solutions/5010020/monotonic-stack-using-pyplot-explain-3ms-beats-99-10/

[monotonic stack Playlist]https://www.youtube.com/watch?v=UApJLN2boco&list=PLYRlUBnWnd5IgqSsJCmHzZMjbnuxLypeM&index=1

[Leetcode程式 playlist]https://www.youtube.com/watch?v=527BNZYm6aE&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=3