【LeetCode】42. Trapping Rain Water

问题描述

https://leetcode.com/problems/trapping-rain-water/#/description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

问题分析

左右两个指针left和right，保留一个左边最大值lmax，一个右边最大值rmax
循环比较：

• 当lmax <= rmax时，说明左边的当前位置肯定可以装满水，加上可以装满的水（lmax - 当前水位），左指针前移；
• 同理，lmax > rmax时，右边的当前位置肯定可以装满水，加上可以装满的水高度（rmax - 当前水位），右指针后移；
• 直到两个指针相遇。

代码

public class Solution {
	    public int trap(int[] height) {
	        int r = 0;
	        int left = 0;
	        int right = height.length - 1;
	        int lmax = 0, rmax = 0;
	        while(left < right) {
	        	lmax = Math.max(lmax, height[left]);
	        	rmax = Math.max(rmax, height[right]);
	        	if(lmax <= rmax) {
	        		r += lmax - height[left];
	        		left++;
	        	} else {
	        		r += rmax - height[right];
	        		right--;
	        	}
	        }
	        return r;
	    }
	}