LeetCode_407: Trapping Rain Water II

        一道很有意思的题目,题目是计算容器雨水积累量,实际上是利用广度优先搜索来不断收缩边界,计算雨水的积累。由于博主之前图一类的题目接触的比较少,这道题目看了一眼答案。这篇博客除了介绍这道题目本身,还将介绍stl中的优先队列priority queue,优先队列是广度优先搜索(BFS)必要的辅助。作为编程辅助,后面还顺便介绍了C++11的花括弧初始化。

STL优先队列

一般队列是先入先出,优先队列是一种具有优先级的队列,出队列的顺序是按照优先级大小来决定的,具体定义参照算法导论堆排序章节,下面介绍stl中的优先队列priority_queue。

priority_queue的使用

  1. 需要在头文件中#include<queue>
  2. 默认采用大优先级队列(大顶堆)
  3. 优先队列中只使用了小于号(<),如果需要使用小优先级队列(小顶堆),只需要重载小于号就可以了
  4. 还有一种使用小优先级队列的方法,就是在构造时指定比较函数,这优点类似于sort中的自定义比较大小函数,后面的代码中会使用这种方法
//定义结构,使用运算符重载,自定义优先级1  
struct cmp1{  
    bool operator ()(int &a,int &b){  
        return a>b;//最小值优先  
    }  
};  
struct cmp2{  
    bool operator ()(int &a,int &b){  
        return a<b;//最大值优先  
    }  
};  
//定义结构,使用运算符重载,自定义优先级2  
struct number1{  
    int x;  
    bool operator < (const number1 &a) const {  
        return x>a.x;//最小值优先  
    }  
};  
struct number2{  
    int x;  
    bool operator < (const number2 &a) const {  
        return x<a.x;//最大值优先  
    }  
};  

int main()  
{   priority_queue<int>que;//采用默认优先级构造队列, 默认使用vector做容器  
  
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
  
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误,  greater为函数从大到小排序
                                                      //这是右移运算符,所以这里用空格号隔开  
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先 less则相反
...

priority_queue的方法

priority_queue调用了STL中的make_heap(), pop_heap(), push_heap()等操作实现了一个优先队列,如上面贴的代码,在构造时,必须声明类型,可以选择声明容器(一般使用默认的vector,也可以使用dqueue,如果使用list编译不报错,但是无法使用),同时还可以选择比较函数,在选择比较函数时,默认使用less(大值优先)。

我们需要了解如下方法:

  • empty(),是否空,true对应空
  • push(a),将a元素送入队列
  • pop(),将最大元素删除
  • top(),返回最大元素(没有删除)
  • size(),返回元素个数
  • front(),back()是由queue提供的方法

C++11特性:统一花括弧初始化

主要是在采用vector做容器时,在C++11中可以直接使用花括弧初始化vector ,pair等元素,花括弧还可以初始化各种变量,同时应该认识到,花括弧比赋值符号更加严格,如果类型不同则会报错。另一方面,博主给出的答案代码如果你无法编译通过,那么可能是由于你的编译器不支持C++11。

在现在的C++中,struct和class唯一的不同就是,前者成员默认public,后者成员默认private。它们在C++03中可以使用如下初始化方法

struct A
{
    int x;
    int y;
};

A a{123,456};  //a.x=123; a.y=456

而在C++11中统一和推广了花括弧初始化:

//下面三行来自C++03:
int a1=1;
int a2=int(1);
int a3(1);
//下面是C++11新增的:
int a4={1};
int a5{1};

以上写法适用于所有结构体和类,如果构造函数中有两个参数

A a2=A(1,2);
A a3(1,2);
A a4={1,2};
A a5{1,2};

C++11还增加了新特征

A func()
{
    //C++03风格:
    return A(123,456);
    //C++11风格:
    return {123,456};
}

当然,使用花括弧初始化有着更加严格的要求,就是类型要统一

long double ld = 3.1415926536;
int a {ld}, b = {ld}    //编译器报错,存在丢失信息的风险
int c (ld), d = ld ;    //正确

这种花括弧初始化的方式还可以推广到vector和list

vector<vector<int>> dir{ { 0, -1 }, { -1, 0 }, { 0, 1 }, {1, 0} };
vector<vector<int>> heights = {
	{12, 13, 0, 12},
	{13, 4, 13, 12},
	{13, 8, 10, 12},
	{12, 13, 12, 12},
	{13, 13, 13, 13}
};

题目

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3×6 height map: [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1] ] Return 4.

填雨水之前:

填雨水之后,有4点雨水积攒下来:

分析

利用广度优先搜索由外向内收缩边界,边界上的最矮高度就是当前边界内可储水的高度。优先队列的作用就是存储边界点,实时提供和更新边界上的最低高度(因为有可能有多个连通域,中间连通域储水的水平面高于外围连通域)。优先队列的作用:优先队列存储了搜索的边界,由外向内进行收缩,不断搜索。在搜索的同时,不断判断当前边界内的可储水高度,进行累加。

  1. 将最外围边界加入最小优先队列。
  2. 从最低点开始进行BFS,最低点周围填充高度肯定等于最低点。
  3. 搜索过程中不断更新边界(当前搜索出发点出队,搜索点周围点入队),并更新边界内可储水高度。
  4. 每个位置的水量等于可储水高度减去底部高度。每个格子进行累加,即为总储水高度。

解答

按照上面的思路编程,使用了stl的优先队列,运行时间22ms,还算比较快的了。

class Solution{
public:
	int trapRainWater(vector<vector<int>>& heightMap){
		int val = 0;
		const int cols = heightMap.size();
		if (cols < 3){
			return 0;
		}
		const int rows = heightMap[0].size();
		if (rows < 3){
			return 0;
		}
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
		for (int i = 0; i < cols; ++i){
			q.push({heightMap[i][0], i * rows});
			q.push({heightMap[i][rows-1], i * rows + rows-1});
		}
		for (int i = 1; i < rows - 1; ++i){
			q.push({heightMap[0][i], i});
			q.push({heightMap[cols-1][i], (cols-1)*rows + i});
		}

		// bfs 
		vector<vector<int>> dir{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
		vector<vector<bool>> visited(cols, vector<bool>(rows, false));
		int mx = INT_MIN;
		while (!q.empty()){
			const auto t = q.top(); q.pop();
			mx = max(mx, t.first);

			const int c = t.second / rows; //xx
			const int r = t.second % rows; //yy
			for (int i = 0; i < 4/*dir.size()*/; ++i){
				const int x = c + dir[i][0];
				const int y = r + dir[i][1];
				if (x < 1 || x >= cols-1 || y < 1 || y >= rows-1 || visited[x][y]){
					continue;
				}
				visited[x][y] = true;
				if (heightMap[x][y] < mx){
					val += mx - heightMap[x][y];
				}
				q.push({heightMap[x][y], x * rows + y});
			}
		}
		return val;
	}
};

 

 

 

 

发表评论