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

STL优先队列

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

priority_queue的使用

  1. 需要在头文件中#include<queue>
  2. 默认采用大优先级队列(大顶堆)
  3. 优先队列中只使用了小于号(<),如果需要使用小优先级队列(小顶堆),只需要重载小于号就可以了
  4. 还有一种使用小优先级队列的方法,就是在构造时指定比较函数,这优点类似于sort中的自定义比较大小函数,后面的代码中会使用这种方法

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中可以使用如下初始化方法

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

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

C++11还增加了新特征

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

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

题目

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,还算比较快的了。

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注