接雨水问题

问题描述：42. 接雨水

该问题的解决思路有如下三种：

  • 双指针解法
  • 动态规划
  • 单调栈解法

双指针解法：对于每个位置找到左边的最大值(LeftMax)和右边的最大值(RightMax)。计算每一个位置可以接到的雨水值为(min(RightMax,LeftMax)-height[i])*1，最后将所有的位置可以接到雨水累加起来。

例如，下图中4的左侧最大值位置在3，右侧最大值位置在7，因此4处的雨水量为$(min(2,3)-2)*1$

42.接雨水3

代码如下：时间复杂度为$O(n^2）$，空间复杂度为$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
        int ans=0;
        int n=height.size();
        for(int i=0;i<n;i++)
        {
            if(i==0 || i == n-1) continue;
            // 左边最高值
            int lHight=height[i];
            // 右边最高值
            int rHight=height[i];
            int j=i-1;
            while(j>=0){lHight=max(height[j],lHight);j--;} 
            j=i+1;
            while(j<n){rHight=max(height[j],rHight);j++;} 
            ans+=min(lHight,rHight)-height[i];
        }

        return ans;
    }

动态规划：对于双指针解法的时间复杂度为$O(n^2)$会导致超时，并且在求取左侧最大值和右侧最大值的过程中存在重复计算，因此采用DP的思路获取每个位置的左侧和右侧最大值，然后再求取可以接到的雨水值。

代码如下：时间复杂度为$O(n)$，空间复杂度为$O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
        int ans=0;
        int n=height.size();
        vector<int> leftMax(n,0);
        vector<int> rightMax(n,0);
        leftMax[0]=height[0];
        rightMax[n-1]=height[n-1];
        for(int i=1;i<n;i++) leftMax[i]=max(height[i],leftMax[i-1]);
        for(int i=n-2;i>=1;i--) rightMax[i]=max(height[i],rightMax[i+1]);
        for(int i=0;i<n;i++)
        {
            //cout<<leftMax[i]<<" ";
            //cout<<rightMax[i]<<" "<<endl;
            if(i==0 || i == n-1) continue;
            ans+=min(leftMax[i],rightMax[i])-height[i];
        }

        return ans;
    }

单调栈：前两种方法是按照列的方式计算，单调栈是采用行的思路计算，示意图如下所示：

42.接雨水2

栈中元素添加的顺序：从栈底向栈头添加元素的方向（从大到小），当出现要添加的元素大于栈头元素时，说明此时出现凹槽，应该弹出栈中元素计算接到的雨水值。

当出现和入栈元素相等的元素时，此时应该保存原数组中最右侧的值，因为在求宽度时遇到相同的柱子时采用右侧的柱子计算，如下图所示：

42.接雨水5

使用单调栈计算接到雨水时需要栈顶元素(mid)以及栈顶的下一个元素，那么雨水的高度为min(左侧高度，右侧高度)-槽底的高度；

接到雨水的宽度为:当前位置-凹槽左侧-1;

1
2
int high=min(hight[i],heigh[st.top()])-height[mid];
int wight=i-st.top()-1;

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int trap(vector<int>& height) {
        int ans=0,n=height.size();
        stack<int> st;
        st.push(0);
        for(int i=1;i<n;i++)
        {
            if(height[i]<height[st.top()]) st.push(i);
            else if(height[i] == height[st.top()]){
                st.pop();
                st.push(i);
            }else{
                
                while(!st.empty() && height[st.top()]<height[i])
                {
                    // 要开始计算可以接到的雨水
                    int mid=st.top(); //记录中间的位置
                    st.pop(); // 弹出该位置
                    if(!st.empty()) // 说明能组成凹槽
                    {
                        int w=i-st.top()-1;
                        int h=min(height[i],height[st.top()])-height[mid];
                        ans+=w*h;
                    }
                }
                st.push(i);
            }
        }
        return ans;
    }

https://hexo.io/docs/one-command-deployment.html)