算法面试题（积水问题）

问题描述：在下图里我们有不同高度的挡板。这个图片由一个整数数组所代表，数组中每个数是墙的高度。下图可以表示为数组（2、5、1、2、3、4、7、2）。假如开始下雨了，那么挡板之间的水坑能够装多少水（水足够多）呢？

 

下图是装满水的情况，一个蓝色格子代表一个单位的水。下图中一共装了10个单位的水。

 

上周参加某大型互联网公司面试，结果死在这道算法上。

我给出的算法： 积水面积 = 总面积 - 砖面积 - 无砖无水面积

思想就是化复杂为简单，直接求积水面积不太好求，那就求比它更简单的。

比如总面积，砖的面积都非常简单。

无砖无水面积也不难求，从两侧最小的开始，遇到比自己大的，开始递归。

// 面试时的算法(积水面积=总面积-砖面积-无砖无水面积)
	public static int fill1(int[] nums) {
		if (nums.length < 3) {
			return 0;
		}
		int max = 0;
		int sum = 0;
		for (int i = 0; i <= nums.length - 1; i++) {
			max = Math.max(max, nums[i]);
			sum += nums[i];
		}
		// 积水面积=总面积-砖面积-无砖无水面积
		return max * nums.length - sum - fill1(nums, max, 0, nums.length - 1);
	}

	// 求无砖无水面积(从两侧最小值开始计算,遇上更大的开始递归)
	private static int fill1(int[] nums, int max, int start, int end) {
		int sum = 0;
		if (nums[start] <= nums[end]) {
			int v = nums[start];
			sum += max - v;
			for (int i = start + 1; i <= end; i++) {
				if (nums[i] > v) {
					sum += fill1(nums, max, i, end);
					break;
				} else {
					sum += max - v;
				}
			}
		} else {
			int v = nums[end];
			sum += max - v;
			for (int i = end - 1; i >= start; i--) {
				if (nums[i] > v) {
					sum += fill1(nums, max, start, i);
					break;
				} else {
					sum += max - v;
				}
			}
		}
		return sum;
	}

   无砖无水面积的算法，稍微改动下就可以算砖和水的面积。

   于是我改良了下算法：积水面积 = 砖和水面积 - 砖面积

// 改良后的算法(积水面积=砖和水面积-砖面积)
	public static int fill2(int[] nums) {
		if (nums.length < 3) {
			return 0;
		}
		int sum = 0;
		for (int i = 0; i <= nums.length - 1; i++) {
			sum += nums[i];
		}
		// 积水面积=砖和水面积-砖面积
		return fill2(nums, 0, nums.length - 1) - sum;
	}

	// 求砖和水的面积(从两侧最小值开始计算,遇上更大的开始递归)
	private static int fill2(int[] nums, int start, int end) {
		int sum = 0;
		if (nums[start] <= nums[end]) {
			int v = nums[start];
			sum += v;
			for (int i = start + 1; i <= end; i++) {
				if (nums[i] > v) {
					sum += fill2(nums, i, end);
					break;
				} else {
					sum += v;
				}
			}
		} else {
			int v = nums[end];
			sum += v;
			for (int i = end - 1; i >= start; i--) {
				if (nums[i] > v) {
					sum += fill2(nums, start, i);
					break;
				} else {
					sum += v;
				}
			}
		}
		return sum;
	}

   网上找到一个算法：求砖左右的挡板， 每堆砖积水量 = 最低挡板高 - 砖高

   由于多出两个数组存储和遍历左右挡板，因此性能并不可观。算法出处

  

// 网上找到的算法(仅供性能对比)
	public static int fill0(int[] nums) {
		if (nums.length < 3) {
			return 0;
		}
		int[] l = new int[nums.length];
		int[] r = new int[nums.length];
		int result = 0;
		l[0] = 0;
		r[nums.length - 1] = 0;
		for (int i = 1; i <= nums.length - 2; i++) {
			l[i] = Math.max(l[i - 1], nums[i - 1]);
			r[nums.length - 1 - i] = Math.max(r[nums.length - i], nums[nums.length - i]);
		}
		for (int i = 1; i <= nums.length - 2; i++) {
			if (l[i] > nums[i] && r[i] > nums[i]) {
				result += Math.min(l[i], r[i]) - nums[i];
			}
		}
		return result;
	}

    现在来对比下性能。

   

public static void main(String[] args) {
		int[] nums = new int[] { 2, 5, 1, 2, 3, 4, 7, 2 };
		StringBuilder sb = new StringBuilder();
		if (nums.length > 0) {
			sb.append(nums[0]);
		}
		for (int i = 1; i < nums.length; i++) {
			sb.append("," + nums[i]);
		}
		System.out.println(MessageFormat.format("输入参数: {0}", sb));
		System.out.println(MessageFormat.format("网上算法结果: {0}", FillWater.fill0(nums)));
		System.out.println(MessageFormat.format("面试算法结果: {0}", FillWater.fill1(nums)));
		System.out.println(MessageFormat.format("改良算法结果: {0}", FillWater.fill2(nums)));
		int n = 100000000;
		System.out.println(MessageFormat.format("执行次数: {0} 次", n));
		long time = System.currentTimeMillis();
		for (int i = 0; i < n; i++) {
			FillWater.fill0(nums);
		}
		System.out.println(MessageFormat.format("网上算法耗时: {0} ms", System.currentTimeMillis() - time));
		time = System.currentTimeMillis();
		for (int i = 0; i < n; i++) {
			FillWater.fill1(nums);
		}
		System.out.println(MessageFormat.format("面试算法耗时: {0} ms", System.currentTimeMillis() - time));
		time = System.currentTimeMillis();
		for (int i = 0; i < n; i++) {
			FillWater.fill2(nums);
		}
		System.out.println(MessageFormat.format("改良算法耗时: {0} ms", System.currentTimeMillis() - time));
	}

 

    结果如下：

  

输入参数: 2,5,1,2,3,4,7,2
网上算法结果: 10
面试算法结果: 10
改良算法结果: 10
执行次数: 100,000,000 次
网上算法耗时: 5,445 ms
面试算法耗时: 2,382 ms
改良算法耗时: 1,936 ms

 

    面试时给出的算法： 积水面积 = 总面积 - 砖面积 - 无砖无水面积

    虽然不是最优算法，但也是一种思维，不能算完全错误吧