42.Trapping-Rain-Water

42. Trapping Rain Water

题目地址

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

题目描述

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

代码

Approach 1: Brute force

Intuition

Do as directed in question. For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.

Algorithm

• Initialize ans = 0

• Iterate the array from left to right:

  • Initialize max_left = 0 and max_right = 0

  • Iterate from the current element to the beginning of array updating:

    • max_left=max(max_left, height[j])

  • Iterate from the current element to the end of array updating:

    • max_right=max(max_right, height[j])

  • Add min(max_left, max_right) − height[i] to ans

Complexity Analysis

• Time complexity: O_(_n^2). For each element of array, we iterate the left and right parts.

• Space complexity: O(1) extra space.

class Solution {


}

Approach 2: Dynamic Programming

Algorithm

• Find maximum height of bar from the left end upto an index i in the array left_max.

• Find maximum height of bar from the right end upto an index i in the array right_max.

• Iterate over the height array and update ans:

  • Add min(max_left[i], max_right[i]) − height[i] to ans

class Solution {
    public int trap(int[] height) {
        if (height == null) return 0;
        int ans = 0;
        int size = height.length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];

        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }

        right_max[size - 1] = height[size - 1];

        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }

        for (int i = 1; i < size - 1; i++) {
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }

        return ans;
    }
}

Approach #3 Using stacks

Intuition

Instead of storing the largest bar upto an index as in Approach 2, we can use stack to keep track of the bars that are bounded by longer bars and hence, may store water. Using the stack, we can do the calculations in only one iteration.

We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to ans.

class Solution {
  public int trap(int[] height) {
    if (height == null || height.length < 2) return 0;

    Stack<Integer> stack = new Stack<>();
    int water = 0, i = 0;
    while (i < height.length) {
      if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
        stack.push(i++);
      } else {
        int pre = stack.pop();
        if (!stack.isEmpty()) {
            // find the smaller height between the two sides
          int minHeight = Math.min(height[stack.peek()], height[i]);
          // calculate the area
          water += (minHeight - height[pre]) * (i - stack.peek() - 1);
        }
      }
    }
    return water;
  }
}

Approach #4 Using two points

Algorithm

• Initialize left pointer to 0 and right pointer to size-1

• While left<right, do:

  • If height[left] is smaller than height[right]

    • If height[left] ≥ left_max, update left_max

    • Else add left_max − height[left] to ans

    • Add 1 to left.

  • Else

    • If height[right] ≥ right_max, update right_max

    • Else add right_max − height[right] to ans

    • Subtract 1 from right.

Complexity analysis

• Time complexity: O_(_n). Single iteration of O(n)

• Space complexity: O(1) extra space. Only constant space required for left, right, left_max and right_max.

class Solution {
  public int trap(int[] height) {
    int ans = 0;
    int left = 0, right = height.length - 1;
    int left_max = 0, right_max = 0;
    while (left < right) {
      if (height[left] < height[right]) {
        if (height[left] >= left_max) {
          left_max = height[left];
        } else {
          ans += (left_max - height[left]);
        }
        left++;
      } else {
        if (height[right] >= right_max) {
          right_max = height[right];
        } else {
          ans += (right_max - height[right]);
        }
        right--;
      }
    }

    return ans;
  }
}