时间复杂度为O（1），空间复杂度为O（N）。

逻辑：

->让我们从0 index循环到输入值的末尾。
->如果我们发现一堵墙大于或等于前一堵墙
->在名为prev_index的变量中记录该墙的索引
->保持将前一个墙的高度减去当前（第i个）墙添加到可变水。
->有一个临时变量，它也存储与水相同的值。
->循环到最后，如果你没有发现任何墙大于或等于前一个墙，然后退出。
->如果上面的点为真（即，如果prev_index < size of input array），则从water中减去temp变量，并从输入数组的末尾循环到prev_index，并找到大于或等于前一个墙的墙（在本例中，从后面开始的最后一个墙）
这里的概念是，如果右边有一个较大的墙，你可以保留水的高度等于左边较小的墙。
如果右边没有更大的墙，那就从左边开始。现在左边肯定有更大的墙了。你实际上循环了两次，所以O（2N），但渐近O（N），当然还有O（1）空间。
Java代码：

class WaterTrap 
{ 

    public static void waterTrappingO1SpaceOnTime(){
        int arr[] = {1,2,3,2,1,0}; // answer = 14
        int size = arr.length-1;
        int prev = arr[0];  //Let first element be stored as previous, we shall loop from index 1
        int prev_index = 0; //We need to store previous wall's index
        int water = 0;
        int temp = 0;   //temp will store water until a larger wall is found. If there are no larger walls, we shall delete temp value from water
        for(int i=1; i<= size; i++){
            if(arr[i] >= prev){     // If current wall is taller then previous wall, make current wall as the previous wall, and its index as previous wall's index for the subsequent loops
                prev = arr[i];
                prev_index = i;
                temp = 0;   //because larger or same height wall is found
            } else {
                water += prev - arr[i]; //Since current wall is shorter then previous, we subtract previous wall height from current wall height and add to water
                temp += prev - arr[i];  // Store same value in temp as well, if we dont find larger wall, we will subtract temp from water
            }
        }
// If the last wall was larger than or equal to the previous wall, then prev_index would be equal to size of the array (last element)

// If we didn't find a wall greater than or equal to the previous wall from the left, then prev_index must be less than index of last element
        if(prev_index < size){
            water -= temp; //Temp would've stored the water collected from previous largest wall till the end of array if no larger wall was found. So it has excess water. Delete that from 'water' var 
            prev = arr[size];   // We start from the end of the array, so previous should be assigned to the last element. 
            for(int i=size; i>= prev_index; i--){ //Loop from end of array up to the 'previous index' which would contain the "largest wall from the left"
                if(arr[i] >= prev){ //Right end wall will be definitely smaller than the 'previous index' wall 
                    prev = arr[i];
                } else {
                    water += prev - arr[i];
                }
            }

        }
        System.out.println("MAX WATER === " + water);
    }
 public static void main(String[] args)  { 
          waterTrappingO1SpaceOnTime();
   } 

}

字符串

Algorithm: 
1.Create two array left and right of size n. create a variable max_ = INT_MIN.
2.Run one loop from start to end. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_
3.Update max_ = INT_MIN.
4.Run another loop from end to start. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_
5.Traverse the array from start to end.
6.The amount of water that will be stored in this column is min(a,b) – array[i],(where a = left[i] and b = right[i]) add this value to total amount of water stored
7.Print the total amount of water stored.

字符串
代码：

/*** Theta(n) Time COmplexity ***/
        static int trappingRainWater(int ar[],int n)
        {
            int res=0;
            int lmaxArray[]=new int[n];
            int rmaxArray[]=new int[n];
            lmaxArray[0]=ar[0];
            for(int j=1;j<n;j++)
            {
                lmaxArray[j]=Math.max(lmaxArray[j-1], ar[j]);
            }
            rmaxArray[n-1]=ar[n-1];
            for(int j=n-2;j>=0;j--)
            {
                rmaxArray[j]=Math.max(rmaxArray[j+1], ar[j]);
            }
            for(int i=1;i<n-1;i++)
            {
                res=res+(Math.min(lmaxArray[i], rmaxArray[i])-ar[i]);
            }
            return res;
        }

型

python code
class Solution:
def trap(self, h: List[int]) -> int:
    i=0
    j=len(h)-1
    ml=-1
    mr=-1
    left=[]
    right=[]
    while(i<len(h)):
        if ml<h[i]:
            ml=h[i]
        left.append(ml)
        if mr<h[j]:
            mr=h[j]
        right.insert(0,mr)
        i=i+1
        j=j-1
    s=0
    for i in range(len(h)):
        s=s+min(left[i],right[i])-h[i]
    return s

字符串

#Brute Force
def getTrappedWater(arr: List[int], n: int) -> int:
    for i in range(n):
        leftmax=0
        rightmax=0
        for a in range(i,-1,-1):
            if arr[a]>arr[i]:
                leftmax=max(leftmax,arr[a])
        for b in range(i+1,n):
            if arr[b]>arr[i]:
                rightmax=max(rightmax,arr[b])
        temp=min(leftmax,rightmax)-arr[i]
        if temp>0:
            ans+=temp
    return ans
#better Approach
def getTrappedWater(arr: List[int], n: int) -> int:
    ans=0
    leftmax=[0]*(n+1)
    for i in range(n):
        leftmax[i]=max(leftmax[i-1],arr[i])
    rightmax=[0]*(n+1)
    for i in range(n-1,-1,-1):
        rightmax[i]=max(rightmax[i+1],arr[i])
    for i in range(n):
        ans+=min(leftmax[i],rightmax[i])-arr[i]
    return ans
# Optimal Approach
def getTrappedWater(arr: List[int], n: int) -> int:
    ans=0
    leftmax=0
    rightmax=0
    left,right=0,n-1
    while left<=right:
        if leftmax<=rightmax:
            if leftmax>arr[left]:
                ans+=leftmax-arr[left]
            else:
                leftmax=arr[left]
            left+=1
        else:
            if rightmax>arr[right]:
                ans+=rightmax-arr[right]
            else:
                rightmax=arr[right]
            right-=1
    return ans

字符串

WoDoSc很好地画了一张海拔和被困水的图表。水只能被困在两个更高的海拔之间。
我所做的是运行代码并输出结果，这样你就可以看到被困的水是如何计算的。代码从“山”的两端开始。
如果两端的高度相同，则右端会移近中心。您可以将左端移近中心。
第一列是左侧立面的高度和索引。第二列是右侧立面的高度和索引。
第三列是最大最小高度。换句话说，左边或右边的最大高度，以较小的最大值为准。这个数字对确定当地水位很重要。
第四列是总和。
跟着图沿着，你就能看到算法是如何工作的。

0,0   1,11   0   0
1,1   1,11   1   0
1,1   2,10   1   0
0,2   2,10   1   1
2,3   2,10   2   1
2,3   1,9    2   2
2,3   2,8    2   2
2,3   3,7    2   2
1,4   3,7    2   3
0,5   3,7    2   5
1,6   3,7    2   6

6

字符串
下面是代码。将print和println语句放在适当的位置可以帮助你理解代码在做什么。

package com.ggl.testing;

public class RainWater implements Runnable {

    public static void main(String[] args) {
        new RainWater().run();
    }

    @Override
    public void run() {
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.println(trap(height));
    }

    public int trap(int[] height) {
        if (height.length <= 2) {
            return 0;
        }

        int h = 0, sum = 0, i = 0, j = height.length - 1;

        while (i < j) {
            System.out.print(height[i] + "," + i + "   " + height[j] + "," + j
                    + "   ");

            if (height[i] < height[j]) {
                h = Math.max(h, height[i]);
                sum += h - height[i];
                i++;
            } else {
                h = Math.max(h, height[j]);
                sum += h - height[j];
                j--;
            }

            System.out.println(h + "   " + sum);
        }

        return sum;
    }

}

型

我知道这可能不是最好的方式来表示它的图形，但你可以想象的情况下图：

的数据
其中红色条是地形（根据您的示例数组的高程），蓝色条是可以被“困”到地形的“山谷”中的水。
为了简化，该算法从左到右循环所有条形图（如果left较小）或从右到左（如果right较小），变量h存储在循环的每一步期间找到的最大高度，因为水不能高于地形的最大高度，并且要知道可以捕获多少水，它将水的高度（最大高度h）与特定点的地形高程之间的差值求和，以获得实际水量。

该算法的工作原理是从左边（i）和右边（j）处理陆地。i和j是计数器，它们朝着彼此靠近陆地的中间。
h是一个变量，它跟踪迄今为止考虑到下侧而发现的最大高度。
土地是通过让i和j“相向”工作来处理的。当我读代码时，我想象了两堵假想的墙，把水挤向中间，最低的墙向较高的墙移动。算法继续计算水的体积。它使用h - height[x]因为水只能在两个墙之间的最低点的内部被容纳。所以本质上它继续从左边和右边加总水的体积并减去水被更高海拔的地块取代。
也许更好的变量名应该是

• leftWall而不是i
• rightWall而不是j
• waterMaxHeight而不是h

我认为上面的解决方案很难理解。我有一个简单的解决方案，需要O（n）额外的空间和O（n）时间复杂度。

算法步骤

1.维护一个数组，该数组包含当前元素右侧所有元素的最大值.
2.从左侧保持变量max，其包含当前元素左侧的所有元素的最大值。
3.查找数组中已经存在的max from left和max from right的最小值。
4.如果最小值大于数组中的当前值，则添加数组中的差值，并添加与当前值的差值，并从左侧更新max。

import java.util.*;
import java.lang.*;
import java.io.*;


class Solution
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] array= {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		int[] arrayofmax=new int[array.length];
		int max=0;
		arrayofmax[array.length-1]=0;
		for(int x=array.length-1;x>0;x--){
		    if(max<array[x]){
		        max=array[x];
		    }
		    arrayofmax[x-1]=max;
		}
		int ans=0;
		int maxfromleft=0;
		
		for(int i=0;i<array.length-1;i++){
		    if(maxfromleft<array[i]){
		        maxfromleft=array[i];
		    }
		    int min=maxfromleft>arrayofmax[i+1]?arrayofmax[i+1]:maxfromleft;
		    if(min>array[i+1]){
		        ans+=min-array[i+1];
		        array[i+1]=min;
		    }
		}
		System.out.println(ans);
	}
}

字符串
可能我的算法和上面的一样，但是我认为这个实现很容易理解。

在Java中解决了收集雨水的问题。

class Store
{
    static int arr[] = new int[]{0, 1, 0, 2, 2};

    // Method for maximum amount of water
    static int StoreWater(int n)
    {
         int max = 0;
         int f = 0;
         for (int i = 1; i < n; i++)
         {
             max = Math.max(arr[i], max);
             f += Math.max(arr[i], max) - arr[i];
         }
         return f;
    }

    public static void main(String[] args) 
    {
        System.out.println("Maximum water that can be accumulated is " + 
                                        findWater(arr.length));
    }
}

字符串