LeetCode面试题 17.21 直方图的水量

题目
解答

1. package leetcode.editor.cn;
3. //leetcode submit region begin(Prohibit modification and deletion)
4. class Solution {
5.     public int trap(int[] height) {
6.         int length = height.length;
7.         if (length == 0) {
8.             return 0;
9.         }
11.         int[] leftMax = new int[length];
12.         leftMax[0] = 0;
13.         for (int i = 1, end = length - 1; i < end; ++i) {
14.             leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
15.         }
17.         int[] rightMax = new int[length];
18.         rightMax[length - 1] = 0;
19.         for (int i = length - 2; i >= 0; --i) {
20.             rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
21.         }
23.         int result = 0;
24.         for (int i = 1, end = length - 1; i < end; ++i) {
26.             if (leftMax[i] > height[i] && rightMax[i] > height[i]) {
27.                 result += Math.min(leftMax[i], rightMax[i]) - height[i];
28.             }
30.         }
32.         return result;
33.     }
34. }
35. //leetcode submit region end(Prohibit modification and deletion)

复制代码

测试用例

1. package leetcode.editor.cn;
3. import org.junit.Assert;
4. import org.junit.Test;
6. public class SolutionTest {
7.     public SolutionTest() {
8.     }
10.     @Test
11.     public void test() {
12.         Solution s = new Solution();
13.         int result = s.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
14.         Assert.assertTrue(String.valueOf(result), result == 6);
15.     }
16. }

复制代码

本题目初看之下照旧有点唬人的，一下子想不到解答的方法。
把题目分解为两个题目：

• 指定坐标的位置，能不能盛水。
  
• 假如上个命题建立，那么能装多少水。
  

第一个题目从知识出发，很好解答，即凹进去的位置，才华装水；比周边高的位置，肯定不能装水。
第二个题目，对于能装水的点，装多少水，取决于周边的最小高度，然后减去自身的高度，便是当前坐标点可以盛的水。