[数据结构与算法]leetcode 42 接雨水

思路一：单调栈

从头到尾遍历数组，维护一个从栈顶向栈底递增的栈stack，对于元素height[i]，栈存储的是从第0到第i-1连续单调递减的子序列序号，每遍历到一个新的元素height[i]，如果height[i]<=stack.top()，则直接将元素插入栈顶；如果height[i]>stack.top(),则说明此时必然形成一个坑，也就是stack.top()的这个位置能够装下雨水，我们将栈顶元素k弹出，其高度为height[k]，如果此时栈非空，栈顶值被更新，前面还有比height[k]还高的阶梯存在，新的stack.top()和i之间能够形成一个坑装下雨水。
雨水的量=雨水深度*坑的长度；
雨水深度=min{height[height.top()],height[i]}-height[k]；
坑的长度=i-stack.top()-1;

代码一

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        stack<int> s;
        for(int i=0;i<height.siaze();i++)
        {
            while(!s.empty()&&height[i]>height[s.top()])
            {
                int last=s.top();
                s.pop();
                if(s.empty())
                    break;
                int minh=height[i]<height[s.top()]?height[i]:height[s.top()];
                minh=minh-height[last];
                int length=i-s.top()-1;
                ans+=minh*length;
            }
            s.push(i);
        }
        return ans;
    }
};

思路二：动态规划

代码二：

1.从头到尾遍历数组，对于每个位置，其能够收集雨水的数量取决于其左侧阶梯最大值和右侧阶梯之中的最大值，取其中较小者。
2.对于每个位置左侧阶梯最大值可以采取从左到右遍历迭代求解，右侧最大值类似。
3.从头到尾遍历数组，如果当前位置的高度小于左右侧最大值的较小值则可以收集雨水。
4.注意两端无法收集雨水，因此遍历从第1个元素到第length-2个元素

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int length=height.size();
        int leftmax[length];
        leftmax[0]=0;
        int mx=height[0];
        for(int i=1;i<length-1;i++)
        {
            leftmax[i]=mx;
            mx=mx>height[i]?mx:height[i];
        }
        mx=height[length-1];
        for(int i=length-2;i>0;i--)
        {
            int mina=leftmax[i]<mx?leftmax[i]:mx;
            ans=ans+(mina-height[i]>0?mina-height[i]:0);
            mx=mx>height[i]?mx:height[i];
        }
        return ans;
    }
};

思路三：双指针

1.左右两边设置一个指针left、right遍历数组，同时记录左边阶梯的最大值leftmax、右侧阶梯最大值rightmax
2.比较leftmax和rightmax值大小，leftmax指的是下标小于等于left的阶梯最大值，rightmax指的是小标大于等于right的阶梯最大值
3.如果是leftmax小一些，则left++，如果此时left所指位置阶梯低于leftmax，则其能够装下雨水的值为leftmax-height[left]，left右侧的阶梯最大值至少大于大于rightmax，且rightmax已经保证大于leftmax，因此至少能够在leftmax和右侧某一个大于大于rightmax之间的阶梯形成凹陷。
4.注意两端无法收集雨水，因此遍历从第1个元素到第length-2个元素

代码三：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int length=height.size();
        int left=0;
        int right=length-1;
        int leftmax=height[0];
        int rightmax=height[length-1];
        while(left<right)
        {
            if(leftmax<rightmax)
            {
                left++;
                if(height[left]<leftmax)
                    ans+=leftmax-height[left];
                leftmax=height[left]>leftmax?height[left]:leftmax;
            }
            else
            {
                right--;
                if(height[right]<rightmax)
                    ans+=rightmax-height[right];
                rightmax=height[right]>rightmax?height[right]:rightmax;
            }
        }
        return ans;
    }
};