Trapping Water & 2D trapping 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.

左右两边开始往中间靠拢。

如果左端最大值比右端最大值小，左边挪动。
否则右侧往中间挪动。

虽然我一直以来解决方案曾经都是用stack做的，但是写的代码真的挺长，不是最优的。

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2)return 0;

        int l=0,r=height.size()-1;

        int leftMost=height[l],rightMost=height[r];

        int total=0;
        while(l<=r)
        {
            if(leftMost<rightMost)
            {
                int cur=min(leftMost,rightMost)-height[l];
                total+=max(cur,0);
                leftMost=max(leftMost,height[l++]);
            }
            else
            {
                int cur=min(leftMost,rightMost)-height[r];
                total+=max(cur,0);
                rightMost=max(rightMost,height[r--]);
            }
        }

        return total;
    }
};

二维的trapping rain water

解法来自http://www.cnblogs.com/deofly/p/trapping-rain-water-ii.html

Description: Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.

Example Given 5*4 matrix

[12,13,0,12] [13,4,13,12] [13,8,10,12] [12,13,12,12] [13,13,13,13] return 14.

用优先级队列维护，每次出队列都是出当前队列中最小高度的，因此可以保证是其高的减去它。

加入队列的时候，是用其周围高点作为其高度加入队列中。

struct Node
{
   int hi, wi, val;
   Node(int _hi, int _wi, int _val)
   {
       hi = _hi, wi = _wi, val = _val;
   }
};

struct Compare
{
   bool operator()(Node n1, Node n2)
   {
       return n1.val>n2.val;
   }
};

class Solution
{
public:
   int getTrappingWater(vector<vector<int>> &m)
   {
       int h = m.size();
       int w = m[0].size();
       if (h<3 || w<3)return 0;

       priority_queue<Node, vector<Node>, Compare> que;

       vector<vector<bool>> visited(h, vector<bool>(w, false));

       for (int hi = 0; hi<h; hi++)
       {
           que.push(Node(hi, 0, m[hi][0]));

           visited[hi][0] = true;
           que.push(Node(hi, w - 1, m[hi][w - 1]));

           visited[hi][w - 1] = true;
       }

       for (int wi = 1; wi<w - 1; wi++)
       {
           que.push(Node(0, wi, m[0][wi]));
           visited[0][wi] = true;
           que.push(Node(h - 1, wi, m[h - 1][wi]));
           visited[h - 1][wi] = true;
       }

       int total = 0;
       while (!que.empty())
       {
           Node top = que.top();
           que.pop();
           if (top.hi>1 && !visited[top.hi - 1][top.wi])
           {
               total += max(-m[top.hi - 1][top.wi] + top.val, 0);

               visited[top.hi - 1][top.wi] = true;

               que.push(Node(top.hi - 1, top.wi, max(m[top.hi - 1][top.wi], top.val)));
           }

           if (top.hi<h - 1 && !visited[top.hi + 1][top.wi])
           {
               total += max(-m[top.hi + 1][top.wi] + top.val, 0);

               visited[top.hi + 1][top.wi] = true;
               que.push(Node(top.hi + 1, top.wi, max(m[top.hi + 1][top.wi], top.val)));
           }

           if (top.wi>1 && !visited[top.hi][top.wi - 1])
           {
               total += max(-m[top.hi][top.wi - 1] + top.val, 0);
               visited[top.hi ][top.wi - 1] = true;

               que.push(Node(top.hi, top.wi - 1, max(m[top.hi][top.wi - 1], top.val)));
           }

           if (top.wi<w - 1 && !visited[top.hi][top.wi + 1])
           {
               total += max(-m[top.hi][top.wi + 1] + top.val, 0);
               visited[top.hi][top.wi+1] = true;

               que.push(Node(top.hi, top.wi + 1, max(m[top.hi][top.wi + 1], top.val)));
           }
       }
       return total;
   }
};

没有找到OJ，写了一个错误的解决方案！！

首先找到down可以包围的最大值，O(n*m)
遍历每一行，每一行类似一维从两端开始遍历。
记录从第一行开始到当前的垂直方向最大值。

对于 [12,13,0,12] [13,4,13,12] [13,8,10,12] [12,13,12,12] [13,13,13,13]

情况来说，（1,1)点不仅是有其上下左右确定的，同时可能流到(2,1)->(2,2)->(2,3)，所以其最大值是12

int getMostWater(vector<vector<int>> &m)
{
    int h=m.size(),w=m[0].size();

    if(h<3 || w<3)return 0;

    vector<vector<int>> down(h,vector<int>(w));

    for(int hi=h-2;hi>=0;hi--)
    {
        for(int wi=0;wi<w;wi++)
        {
            down[hi][wi]=max(down[hi+1][wi],m[hi+1][wi]);
        }
    }

    vector<int> up(w);
    int total=0;
    for(int hi=1;hi<hi-1;hi++)
    {
        for(int wi=0;wi<w;wi++)
        {
            up[wi]=max(up[wi],m[hi-1][wi]);
        }

        int l=0,r=w-1;
        int leftMost=m[hi][0],rightMost=m[hi][r];

        while(l<=r)
        {
            if(leftMost<rightMost)
            {
                int cur=min(leftMost,min(up[l],down[hi][l]))-m[hi][l];
                total+=max(cur,0);

                leftMost=max(leftMost,m[hi][l]);
            }
            else
            {
                int cur=min(rightMost,min(up[r],down[hi][r]))-m[hi][r];
                total+=max(cur,0);

                rightMost=max(leftMost,m[hi][r]);
            }
        }
    }

    return total;
}

Trapping Water

Trapping Water & 2D trapping water

二维的trapping rain water

results matching ""

No results matching ""