[LeetCode] 42. Trapping Rain Water

壮心未与年俱老，死去犹能作鬼雄。这篇文章主要讲述[LeetCode] 42. Trapping Rain Water相关的知识，希望能为你提供帮助。
https://leetcode.com/problems/trapping-rain-water/
思路一：参考 84. Largest Rectangle in Histogram，用 stack 做辅助

public class Solution { public int trap(int[] heights) { int result = 0; Stack< Integer> stack = new Stack< > (); for (int i = 0; i < heights.length; i++) { while (!stack.isEmpty() & & heights[stack.peek()] < heights[i]) { int tmp = stack.pop(); // index of bottom int height = stack.isEmpty() ? 0 : Math.min(heights[stack.peek()], heights[i]) - heights[tmp]; int width = stack.isEmpty() ? 0 : i - stack.peek() - 1; result += height * width; } stack.push(i); } return result; } }

【[LeetCode] 42. Trapping Rain Water】
思路二：dynamic programming