【每日一题 春季15】592. 雨 & 17.21. 直方图的水量

发表于 分类于 Valine：
本文字数： 162 阅读时长 ≈ 1 分钟

Day15 AcWing 592. 雨
Day15 LeetCode 17.21. 直方图的水量

直方图的水量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
left[1]:1
left[2]:1
left[3]:2
left[4]:2
left[5]:2
left[6]:2
left[7]:3
left[8]:3
left[9]:3
left[10]:3
left[11]:3

right[10]:2
right[9]:2
right[8]:2
right[7]:3
right[6]:3
right[5]:3
right[4]:3
right[3]:3
right[2]:3
right[1]:3
right[0]:3

思路

雨
直方图的水量
  1. 从左往右遍历每个位置的左边最高的长方形height
  2. 从右往左遍历每个位置的右边最高的长方形height
  3. 遍历height[i]，取left[i] right[i]最小值，减去height[i]

代码

592. 雨
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 55;

int n, m;
int h[N][N];
int dist[N][N];
bool st[N][N];

struct Node
{
    int x, y, d;
    bool operator< (const Node& t) const {
        return d > t.d;
    }
};

int main()
{
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ )
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                scanf("%d", &h[i][j]);

        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        priority_queue<Node> heap;

        for (int i = 1; i <= n; i ++ )
        {
            heap.push({i, 1, h[i][1]});
            dist[i][1] = h[i][1];
            heap.push({i, m, h[i][m]});
            dist[i][m] = h[i][m];
        }
        for (int i = 2; i < m; i ++ )
        {
            heap.push({1, i, h[1][i]});
            dist[1][i] = h[1][i];
            heap.push({n, i, h[n][i]});
            dist[n][i] = h[n][i];
        }

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int res = 0;
        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();

            if (st[t.x][t.y]) continue;
            st[t.x][t.y] = true;
            res += t.d - h[t.x][t.y];

            for (int i = 0; i < 4; i ++ )
            {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x >= 1 && x <= n && y >= 1 && y <= m)
                {
                    if (dist[x][y] > max(t.d, h[x][y]))
                    {
                        dist[x][y] = max(t.d, h[x][y]);
                        heap.push({x, y, dist[x][y]});
                    }
                }
            }
        }
        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}
17.21. 直方图的水量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        int n=height.size();
        int res=0;
        vector<int> right(n),left(n);
        left[0]=height[0],right[n-1]=height[n-1];
        for(int i=1;i<n;i++)
            //left[i]=max(left[i-1],height[i]),printf("left[%d]:%d\n",i,left[i]);
            left[i]=max(left[i-1],height[i]);
        for(int i=n-2;i>=0;i--)
            //right[i]=max(right[i+1],height[i]),printf("right[%d]:%d\n",i,right[i]);
            right[i]=max(right[i+1],height[i]);
        for(int i=0;i<n;i++)
            res+=min(left[i],right[i])-height[i];
        return res;
    }
};