当前位置:网站首页>leetcode:407. Connected to rainwater II
leetcode:407. Connected to rainwater II
2022-07-21 15:05:00 【Oceanstar's study notes】
Title source
Title Description
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
}
};
title
It's similar to a one-dimensional array , We just want to know how much water can be stored in each grid at most , And then add up . But how much water can this store at most? How to ask ?
Priority queue + Search from outside to inside
problem : Which grids can receive water ?
- The boundary must not
- The premise that lattice can store water : Boundary , And the lowest boundary is higher than yourself
idea :
- Spread from the boundary to the inside
- Only those lower than the boundary can store water
- According to the barrel principle :
- Every time you spread inside, you should find the lowest height in the boundary ( It is the bottleneck , It can be solved with the smallest heap ), Start from this point and spread inward
- Find adjacent nodes when spreading , If it is lower than the lowest in the current boundary , Explain that water can be filled . otherwise , This location will become the new boundary .
- We can ensure the correctness by putting each position into the stack only once . Correctness comes from two points :
- The boundary we maintain in the priority queue is a complete boundary . Each time, all adjacent points of the border will be queued , There will be no gap in the boundary .
- On the premise that there is no gap in the boundary , Judge whether a location can store water , Of course, you only need to judge and compare with the lowest position in the boundary .
- How to ensure that a location is only stacked once ? Use one vis Array can solve
The whole idea
- In the whole process, two variables need to be maintained :water( The total amount of water )、max( bottleneck )
- At the beginning max = 0, water by 0
- First enclosure : Take the outermost column to get a circle of wooden barrels , Merge into heap
- Find the shortest column on the circle : That is, find the shortest board of the barrel , Top the heap and update max( The pop-up element is the new bottleneck )
- For the column in the adjacent circle of the shortest column in the circle , Try to fill it with water ( Settlement water)
- According to the barrel principle , Can you fill it with water , It depends on the shortest board of the barrel ( That is, the shortest column on the circle )、 The bottom of the barrel ( That is, columns in adjacent circles ) Height
- If the column in the adjacent circle is lower than the shortest column in the circle , It can fill water without water flowing out of the circle , At most, water can be filled to a height equal to the shortest column on the circle
- Shrink ring : Pile columns in adjacent circles ( If irrigation is available , The height is the height after irrigation )
In fact, it's the same thing with the simplest idea of one-dimensional rainwater connection . Are nibbling from the outermost layer to the inside , Find the lowest one from the outermost layer every time , And then nibble at the neighboring . Just the outermost layer of a one-dimensional array , use max Can distinguish , There is only one adjacent to each other . The outermost circle of a two-dimensional array requires a priority queue , adjacent 4 Each direction should be explored
class Solution {
struct Node{
int value;
int row;
int col;
Node(int v, int i, int j) {
value = v;
row = i;
col = j;
}
bool operator> (const Node &other) const {
return this->value > other.value;
}
};
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.empty() || heightMap[0].empty()){
return 0;
}
int N = heightMap.size(), M = heightMap[0].size();
std::vector<std::vector<bool>> isEnter(N, std::vector<bool>(M));
std::priority_queue<Node, std::vector<Node>, std::greater<Node>> minHeap;
for (int j = 0; j < M - 1; ++j) {
// 0 1 2 3 4 M - 2
isEnter[0][j] = true;
minHeap.push(Node(heightMap[0][j], 0, j));
}
for (int i = 0; i < N - 1; ++i) {
// 0:M - 1
isEnter[i][M - 1] = true; // 1:M - 1
minHeap.push(Node(heightMap[i][M - 1], i, M - 1)); // N-2 : M -1
}
for (int j = M - 1; j > 0; --j) {
isEnter[N - 1][j] = true;
minHeap.push(Node(heightMap[N - 1][j], N - 1, j));
}
for (int i = N - 1; i > 0; --i) {
isEnter[i][0] = true;
minHeap.push(Node(heightMap[i][0], i, 0));
}
int water = 0, max = 0;
while (!minHeap.empty()){
auto cur = minHeap.top(); minHeap.pop();
max = std::max(max, cur.value);
int r = cur.row;
int c = cur.col;
if (r > 0 && !isEnter[r - 1][c]) {
water += std::max(0, max - heightMap[r - 1][c]);
isEnter[r - 1][c] = true;
minHeap.push( Node(heightMap[r - 1][c], r - 1, c));
}
if (r < N - 1 && !isEnter[r + 1][c]) {
water += std::max(0, max - heightMap[r + 1][c]);
isEnter[r + 1][c] = true;
minHeap.push( Node(heightMap[r + 1][c], r + 1, c));
}
if (c > 0 && !isEnter[r][c - 1]) {
water += std::max(0, max - heightMap[r][c - 1]);
isEnter[r][c - 1] = true;
minHeap.push( Node(heightMap[r][c - 1], r, c - 1));
}
if (c < M - 1 && !isEnter[r][c + 1]) {
water += std::max(0, max - heightMap[r][c + 1]);
isEnter[r][c + 1] = true;
minHeap.push( Node(heightMap[r][c + 1], r, c + 1));
}
}
return water;
}
};
Union checking set
Why can we use and search sets
Enumerate the height of the water surface from low to high , Use join to look up sets and adjacent “ The pool ”, And maintain the total volume .
The question is , The maximum amount of water that each unit can hold , Consider first arranging all cells in ascending order , Then simulate the flood process , Raise the water level to the minimum height of the untreated unit each time .
Each time you process a cell , If there are other processed units in the up and down direction , Merge them into the same set , If after merging into the set , The set is connected to the boundary
It indicates that the maximum water holding height of the blue unit set is the current water level ( That is, the height of the orange unit ), Merge the blue unit set into the green unit set , And add the water holding capacity of the blue unit set into the final result
Because it is handled in the order of height from small to large , Therefore, the height of other units around the blue unit set must be greater than or equal to the height of the orange unit
My question ( To be put into practice )
yes leetcode:42. Rainwater collection An extension of
- 1-D There is a solution to the problem of rainwater connection from the left and right boundaries to the middle , In the process of contraction , For each coordinate ( One dimensional coordinates ) It can be solved by rainwater
- Can you Turn two dimensions into one dimension , Then use one-dimensional rainwater method to solve this problem ?
- This question is a stereogram , about heightMap The upper index is (x, y) The point of , We cannot simply consider m i n ( ( x , y ) The maximum values in four directions ) ) min((x,y) The maximum values in four directions )) min((x,y) The maximum values in four directions )), Here is an example for you to see at a glance :
- For the height in the figure is 4 The point of , Although the maximum value in all four directions is 13, But in fact, the height of water can only reach 12( Slanting edge ) Of , thus it can be seen , This question considers more than four directions , But the whole plane .
Change two dimensions to one dimension to be added ( Prove it can't )
边栏推荐
- Let's talk about bron filter
- service和systemctl的区别/修改PATH的方法/一条命令查看IP地址和网关以及DNS服务器
- 欧菲光:已布局运动相机、智能家居等光学镜头 / 影像模组,部分产品已实现量产
- Web3流量聚合平台Starfish OS,给玩家元宇宙新范式体验
- Hutoo - date time tool -dateutil
- PLC的通信模式
- 广发期货网上开户安全吗?有没有开户指引?
- 【硬件基础4】二极管(原理、特性、类型、电路分析)
- Modularization of node
- leetcode:689. Maximum sum of three non overlapping subarrays
猜你喜欢
leetcode:689. Maximum sum of three non overlapping subarrays
NPM and package
Semantic matching of English keyword text splitting
C语言详解系列——goto语句的讲解和循环语句的简单练习题
Nacos cluster construction
Web3流量聚合平台Starfish OS,给玩家元宇宙新范式体验
上榜 首批获得实体证书的博客专家
Yunna | dynamic environment monitoring system inspection, general introduction to the functions of the dynamic environment monitoring system
service和systemctl的区别/修改PATH的方法/一条命令查看IP地址和网关以及DNS服务器
据说只有大神才知道这个电容的作用
随机推荐
SQL: SELECT t.`app_ code`, SUM(t.`success_num`) AS success_ num, SUM(t.`
do-while 怎么调用编写的 odps sql 呢?
Web3 traffic aggregation platform starfish OS gives players a new paradigm experience of metauniverse
SAP 电商云 Spartacus UI SiteContextUrlParams 的实现明细介绍
王炸动力 创富快人一步!祥菱大熊猫2.0动力产品正式上市
当删则删,这种电容本不该出现
云原生如何支撑企业 IT 治理 | 阿里云用户组
全棧開發實戰 | SSM框架整合完整教程
Intel汇编语言程序设计学习-第五章 过程-上
金仓数据库KingbaseES数据库管理员指南--15.1. 管理视图
It is said that only the great God knows the function of this capacitor
【Kaggle】如何有效避免OOM(out of memory)和漫长的炼丹过程
Nacos cluster construction
Hutoo - date time tool -dateutil
欧菲光:已布局运动相机、智能家居等光学镜头 / 影像模组,部分产品已实现量产
SAP 电商云 Spartacus UI Store 相关的设计明细
7.19模拟赛总结
[error analysis] grid access
Kingbasees SQL language reference manual of Jincang database (3.5 format model, 3.6 null value, 3.7 comments)
上榜 首批获得实体证书的博客专家