# 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.

```java
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

```java
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](https://leetcode.com/problems/trapping-rain-water/solution/#approach-2-dynamic-programming), 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.

```java
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.

```java
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;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/two-pointers/42.trapping-rain-water.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.