[PHP知识库]接雨水【leetcode高级--php版】

在此提供动态规划、单调栈、双指针三种解法：

1. 动态规划：以leftMax[i]表示i及其左边的高度最大值， 以rightMax[i]表示i及其右边的高度最大值，则点i处能接的雨水为 min($leftMax[$i], $rightMax[$i]) - $height[$i];

	function trap($height) {
		$len = count($height);

		$leftMax = $rightMax = [];
		$leftMax[0] = $height[0];
		$rightMax[$len-1] = $height[$len-1];

		for ($i=1; $i<$len; $i++) {
			$leftMax[$i] = max($leftMax[$i-1], $height[$i]);
			$rightMax[$len-1-$i] = max($rightMax[$len-$i], $height[$len-1-$i]);
		}

		$ans = 0;
		for ($i=1; $i<$len-1; $i++) {
			$ans += min($leftMax[$i], $rightMax[$i]) - $height[$i];
		}

		return $ans;
	}

2. 单调栈：

	function trap2($height) {
		$stack = new SplStack();
		$len = count($height);
		if ($len <= 2) {
			return 0;
		}
		$ans = 0;
		$stack->push(0);
		for ($i=1; $i<$len; $i++) {
			$topIdx = $stack->top();
			while ($height[$i] > $height[$topIdx]) {
				$topIdx = $stack->pop();
				if ($stack->count() >= 1) {
					$nextIdx = $stack->top();
					$ans += (min($height[$i], $height[$nextIdx]) - $height[$topIdx]) * ($i-$nextIdx-1);
					$topIdx = $stack->top();
				}
				if ($stack->isEmpty()) {
					break;
				}
			}
			$stack->push($i);
		}
		return $ans;
	}

3. 双指针法：

	function trap3($height) {
		$len = count($height);
		if ($len <= 2) {
			return 0;
		}

		$leftMax = $height[0];
		$rightMax = $height[$len-1];
		$leftIdx = 1;
		$rightIdx = $len-2;
		$ans = 0;

		while ($leftIdx <= $rightIdx) {
			if ($leftMax <= $rightMax) {
				if ($height[$leftIdx] >= $leftMax) {
					$leftMax = $height[$leftIdx];
				} else {
					$ans += $leftMax - $height[$leftIdx];
				}
				++$leftIdx;
			} else {
				if ($height[$rightIdx] >= $rightMax) {
					$rightMax = $height[$rightIdx];
				} else {
					$ans += $rightMax - $height[$rightIdx];
				}
				--$rightIdx;
			}
		}
		return $ans;
	}