刷题skill+编程cultivation+记录

05/01/2019 Day46
LeetCode 42. Trapping Rain Water
Importantce【5】

解题思路：
双指针的题目。
主要是考虑每一个位置可以存的水的体积是 min{leftMax, rightMax} - height[i]

1. class Solution {
   
2.     public int trap(int[] height) {
   
3.         // time: O(n) 99.85%
   
4.         // space: O(1) 89.09%
   
5.         int res = 0;
   
6.         if (height == null || height.length == 0) return res;
   
7.         
   
8.         int left = 0, right = height.length - 1;
   
9.         int leftMax = 0, rightMax = 0;
   
10.         while (left < right) {
    
11.             if (height[left] < height[right]) { // height[right] <= rightMax_before
    
12.                 leftMax = Math.max(leftMax, height[left]);
    
13.                 res += leftMax - height[left];
    
14.                 left++;
    
15.             } else {
    
16.                 rightMax = Math.max(rightMax, height[right]);
    
17.                 res += rightMax - height[right];
    
18.                 right--;
    
19.             }
    
20.         }
    
21.         return res;
    
22.     }
    
23. }

复制代码

KMP算法在第 6 页，第60垄