一道很有意思的题目,题目是计算容器雨水积累量,实际上是利用广度优先搜索来不断收缩边界,计算雨水的积累。由于博主之前图一类的题目接触的比较少,这道题目看了一眼答案。这篇博客除了介绍这道题目本身,还将介绍stl中的优先队列priority queue,优先队列是广度优先搜索(BFS)必要的辅助。作为编程辅助,后面还顺便介绍了C++11的花括弧初始化。
STL优先队列
一般队列是先入先出,优先队列是一种具有优先级的队列,出队列的顺序是按照优先级大小来决定的,具体定义参照算法导论堆排序章节,下面介绍stl中的优先队列priority_queue。
priority_queue的使用
- 需要在头文件中#include<queue>
- 默认采用大优先级队列(大顶堆)
- 优先队列中只使用了小于号(<),如果需要使用小优先级队列(小顶堆),只需要重载小于号就可以了
- 还有一种使用小优先级队列的方法,就是在构造时指定比较函数,这优点类似于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点雨水积攒下来:
分析
利用广度优先搜索由外向内收缩边界,边界上的最矮高度就是当前边界内可储水的高度。优先队列的作用就是存储边界点,实时提供和更新边界上的最低高度(因为有可能有多个连通域,中间连通域储水的水平面高于外围连通域)。优先队列的作用:优先队列存储了搜索的边界,由外向内进行收缩,不断搜索。在搜索的同时,不断判断当前边界内的可储水高度,进行累加。
- 将最外围边界加入最小优先队列。
- 从最低点开始进行BFS,最低点周围填充高度肯定等于最低点。
- 搜索过程中不断更新边界(当前搜索出发点出队,搜索点周围点入队),并更新边界内可储水高度。
- 每个位置的水量等于可储水高度减去底部高度。每个格子进行累加,即为总储水高度。
解答
按照上面的思路编程,使用了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; } };