# LeetCode42

xiaoxiao2021-02-28  6

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

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!

## 中文介绍

01021013212101122223333301112222011

## 对应代码

class Solution42 { public static void main(String[] args){ Solution42 solution42 = new Solution42(); int[] a = {6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3}; System.out.println(solution42.trap(a)); } public int trap(int[] height) { int result =0; Stack<Integer> stack2 = new Stack(); Stack<Integer> stack = new Stack(); for(int i=0;i<height.length;i++){ if(stack.isEmpty()||height[i]<stack.peek()){ stack.add(height[i]); stack2.add(i); }else { int preH =0; int r =0; while(!stack.isEmpty()&&height[i]>=stack.peek()){ int h = stack.pop(); r += (h-preH)*(i-stack2.pop()-1); preH = h; } if(!stack.isEmpty()&&height[i]>preH){ r+=(height[i]-preH)*(i-stack2.peek()-1); } stack.add(height[i]); stack2.add(i); result+=r; } } return result; } }

## 其他解法

### Brute force [Accepted] 暴力破解

Algorithm 暴力破解的思想就是从左边开始遍历，然后寻找元素左右两边的最大值 然后用左右两边高度最大值的较小者减去当前的高度， 把这些高度累加起来，就是最后的结果。

c++

int trap(vector<int>& height) { int ans = 0; int size = height.size(); for (int i = 1; i < size - 1; i++) { int max_left = 0, max_right = 0; for (int j = i; j >= 0; j--) { //Search the left part for max bar size max_left = max(max_left, height[j]); } for (int j = i; j < size; j++) { //Search the right part for max bar size max_right = max(max_right, height[j]); } ans += min(max_left, max_right) - height[i]; } return ans; }

## 动态规划

c++

int trap(vector<int>& height) { if(height == null) return 0; int ans = 0; int size = height.size(); vector<int> left_max(size), right_max(size); left_max[0] = height[0]; for (int i = 1; i < size; i++) { left_max[i] = 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] = max(height[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += min(left_max[i], right_max[i]) - height[i]; } return ans; }

## 利用两个指针

int trap(vector<int>& height) { int left = 0, right = height.size() - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (height[left] < height[right]) { height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]); ++left; } else { height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]); --right; } } return ans; }