ok

NoteXYX · NoteXYX · commit d10cba5a5e8e · 2020-08-09T17:14:03.000+08:00
diff --git a/src/com/leetcode/Main42.java b/src/com/leetcode/Main42.java
@@ -0,0 +1,30 @@
+package com.leetcode;
+
+import java.util.Stack;
+
+/**
+ * 42. 接雨水
+ */
+public class Main42 {
+    public int trap(int[] height) {
+        int sum = 0;
+        Stack<Integer> stack = new Stack<>();
+        int current = 0;
+        while (current < height.length) {
+            //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
+            while (!stack.empty() && height[current] > height[stack.peek()]) {
+                int h = height[stack.peek()]; //取出要出栈的元素
+                stack.pop(); //出栈
+                if (stack.empty()) { // 栈空就出去
+                    break;
+                }
+                int distance = current - stack.peek() - 1; //两堵墙之前的距离。
+                int min = Math.min(height[stack.peek()], height[current]);
+                sum = sum + distance * (min - h);
+            }
+            stack.push(current); //当前指向的墙入栈
+            current++; //指针后移
+        }
+        return sum;
+    }
+}
