[Leetcode] String & Array

satjd

2018/12/13

Categories: Algorithm 基础知识 Tags: leetcode

42. Trapping Rain Water

/**
 * 解法1:
 * 使用两个辅助数组leftmax[]和rightmax[]
 * leftmax[i]和rightmax[i]分别表示height[i]左侧和右侧的最大值
 * 那么对于每一个height[i],能放水的体积是min(left[i],right[i])-height[i]
 * 时间复杂度O(n) 空间复杂度O(n)
 * 
 * 解法2:
 * 使用一个栈,将解法1的两次循环优化成一次
 * 时间复杂度O(n),常数级别优于解法1  空间复杂度O(n),需要维护一个O(n)大小的栈 
 *  
 * 解法3(该文件中的解法):
 * 双指针法,初始化两个指针left = 0,right = height.length-1
 * 再使用两个变量leftMax和rightMax,leftMax表示height[left]左侧的最大值
 * rightMax表示height[right]右侧的最大值
 * 
 * 这种方法与解法2的根本区别在于,
 * 不需要同时算出真正的左侧最大和右侧最大
 * 就能知道究竟哪边是这个需要注水位置的“短板”,那么,我们算出一边的最大值即可
 * 双指针的巧妙之处在于,保持了对于height[left]和其左侧的元素都比height[right]要小
 * 这样,height[left]的短板就一定出在height[left]的左侧范围内
 * 同理,height[right]的短板就一定出在height[right]的右侧范围内
 * 那么究竟是如何调整left和right才能保持上述状态呢
 * 我们在一个while循环中比较当前height[left]和height[right]的大小,
 * 如果height[right]更大,则移动left,这也就保证了移动的时候left走过的元素一定都比height[right]小
 * 同理,如果height[left]更大,则移动right,保证right走过的元素比height[left]小
 * 
 * 时间复杂度O(n) 空间复杂度O(1) 仅有两个指针和两个max值的额外开销
 */
class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0, rightMax = 0, ret = 0;
        
        while (left < right) {
           if (height[left] < height[right]) {
               if (left == 0 || height[left] > leftMax) {
                   leftMax = height[left];
               } else {
                   ret += (leftMax - height[left]);
               }
               left ++;
           } else {
               if (right == height.length - 1 || height[right] > rightMax) {
                   rightMax = height[right];
               } else {
                   ret += (rightMax - height[right]);
               }
               right --;
           }
        }
        return ret;
    }
}