Here I gathered some of (what I thought are) best answers to LeetCode questions:
- https://leetcode.com/problems/wiggle-subsequence/discuss/84887/C++-0ms-O(N)-dynamic-programming-solution
- an O(n) solution
- https://leetcode.com/problems/trapping-rain-water/description/
- an O(n) solution of a similar (but harder) question, found in the book <算法竞赛入门经典(第二版) pp249例8-18
- basic idea is to find a maximal height which can reserve the water for each position i, if the max height equals to the unit then no rain can be collected at i
(vice versa, from right to left)