Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to collect Rain Water on C++". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Trapping Rain Water collects 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

This collection of Rain Water's question is somewhat similar to the previous Largest Rectangle in Histogram, but not quite the same. Let's first look at a method based on dynamic programming Dynamic Programming to maintain an one-dimensional dp array. This DP algorithm needs to traverse the array twice, the first time to store the maximum value to the left of the I position in the dp [I], and then start to traverse the array for the second time to find the maximum value on the right. Then compare the smaller value with the maximum value on the left, and then compared with the current value A [I], if it is greater than the current value, the difference is stored in the result, as shown in the code below:

C++ solution one:

Class Solution {public: int trap (vector& height) {int res = 0, mx = 0, n = height.size (); vector dp (n, 0); for (int I = 0; I

< n; ++i) { dp[i] = mx; mx = max(mx, height[i]); } mx = 0; for (int i = n - 1; i >

= 0;-- I) {dp [I] = min (dp [I], mx); mx = max (mx, height [I]); if (dp [I] > height [I]) res + = dp [I]-height [I];} return res;}}

Java solution 1:

Public class Solution {public int trap (int [] height) {int res = 0, mx = 0, n = height.length; int [] dp = new int [n]; for (int I = 0; I

< n; ++i) { dp[i] = mx; mx = Math.max(mx, height[i]); } mx = 0; for (int i = n - 1; i >

= 0;-- I) {dp [I] = Math.min (dp [I], mx); mx = Math.max (mx, height [I]); if (dp [I]-height [I] > 0) res + = dp [I]-height [I];} return res;}}

Let's look at a solution that only needs to be traversed once. This algorithm requires two pointers left and right to point to the beginning and end of the array, scanning from both sides to the middle. Within the range determined by the current two pointers, first compare the two sides to find a smaller value. If the smaller value is the value pointed to by left, scan from left to right. If the smaller value is the value pointed to by right, scan from right to left. If the value encountered is smaller than the smaller value, scan from left to right. The difference is stored in the result, and if the value encountered is large, the new window range is redetermined, and so on until the left and right pointers coincide, as shown in the code below:

C++ solution 2:

Class Solution {public: int trap (vector& height) {int res = 0, l = 0, r = height.size ()-1; while (l < r) {int mn = min (height [l], height [r]); if (mn = = height [l]) {+ + l While (l < r & & height [l] < mn) {res + = mn-height [lumped +];}} else {--r; while (l < r & & height [r] < mn) {res + = mn-height [r -] } return res;}}

Java solution II:

Public class Solution {public int trap (int [] height) {int res = 0, l = 0, r = height.length-1; while (l < r) {int mn = Math.min (height [l], height [r]); if (height [l] = = mn) {+ + l While (l < r & & height [l] < mn) {res + = mn-height [lumped +];}} else {--r; while (l < r & & height [r] < mn) {res + = mn-height [r -] } return res;}}

We can further optimize the above solution to make it more concise:

C++ solution 3:

Class Solution {public: int trap (vector& height) {int l = 0, r = height.size ()-1, level = 0, res = 0; while (l < r) {int lower = height [(height [l] < height [r])? Res +: r level -]; level = max (level, lower); res + = level-lower;} return res;}}

Java solution 3:

Public class Solution {public int trap (int [] height) {int l = 0, r = height.length-1, level = 0, res = 0; while (l < r) {int lower = height [(height [l] < height [r])? Res +: r level -]; level = Math.max (level, lower); res + = level-lower;} return res;}}

The following solution is done with stack, and the blogger didn't notice the tag and stack of this question at first, so you should pay more attention to the tag in the summary. Its practical stack method makes it easier for bloggers to understand. The idea is to traverse the height. If the stack is empty at this time, or if the current height is less than or equal to the top height of the stack, then press the coordinates of the current height into the stack. Note that instead of pressing the height directly into the stack, the coordinates are pushed into the stack so that the horizontal distance can be calculated later. When encountered higher than the height of the top of the stack, it means that there may be a pit, you can install Rain Water. At this time, there is at least one height in the stack, if there is only one, then you cannot form a pit and skip it directly. if there is more than one, the top element of the stack is taken out as a pit, and the new element on the top of the stack is the left boundary. the current height is the right boundary. as long as you take the smaller of the two, minus the height of the pit, the length is the right boundary coordinates minus the left boundary coordinates, and the multiplication of the two is full of water. See the code as follows:

C++ solution 4:

Class Solution {public: int trap (vector& height) {stack st; int i = 0, res = 0, n = height.size (); while (I < n) {if (st.empty ()) | | height [I]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.