想问一下大家，对这个题目有什么思路吗？
就是Link里店面的那一道题，模拟直方图灌水。
http://www.1point3acres.com/bbs/ … adio%26sortid%3D311
谢谢大家先
我给一个解法。
首先，直方图上的所有位置都可归为3种类型之一：
- Valley，该位置上的高度小于左右两边。在此处倒水时，水会积存下来；
- Slope，该位置的高度大于一边但小于另一边。在此处倒水时，水会沿着坡度流向最近的Valley。所以， 在Slope处倒水，完全等价于在离其最近的Valley处倒水 。
- Peak，即该位置上的高度大于左右两边的位置都要高。在此处倒水时，水会均匀向两边散开，流向两侧的valley。所以， 在Peak处倒量为N的水，完全等价于在其两侧的最近Valley处各倒N/2量的水 。
注意，这里所说的“一个位置”是“一段具有相同高度的距离”。比如[3, 7]范围内的高度如果都是8，那么[3, 7]算“一个位置”。
但是还没完，随着水量的增加，可能会引起倒水位置本身的类型的转化的。比如一个Valley完全填满以后，就可能会变成一个Slope或Peak；而一个Peak两侧的Valley全部填满后，如果两侧Valley另一头的峰都很高的话，那水量可能会淹过当前这个peak。这样Peak所在的位置反而变成一个Valley了；
因此，简单来说，我们的算法就是判断当前位置的类型，然后找到相应的Valley，向里面加水直到 该位置的类型改变 。然后重复该过程。
具体怎么做呢？考虑只有一个Valley的情况：
这个Valley可以看作由3层组成。[x:2~3,y:1~2]是第一层，这层填满以后第二层是[x:2~4,y:2~3];再上面是[x:1~4,y:3~4]。容易看出， 位置类型改变总是出现在某一层被填满了以后 。所以加水时就以层为单位来加：比如总水量V=5，先计算出第一层的容积V1=1,因为V > V1, 所以这一层肯定会被填满，那么把[x:2~3]处的高度更新为2，剩下V=4；第二层V2=2,那么依然可以填满这一层。所以[x:2~4]处的高度更新为3，剩下V=V-V2=2;第三层V3 = 3，这一层只能填V/(4-1) = 0.667的高度，所以[x:1~4]处的高度更新为3+0.667=3.667。V=0，退出。
但是，如果是同时在两个Valley中倒水，情况就会复杂一些了。这时要同时考虑左Valley中的当前层容积（V左）和右Valley中的当前层（V右）的大小关系。如果V左 < V右，那么当倒水达到2*V左时，V左会先变满，这种情况下，我们要先填平V左的当前层，然后V右的高度会上升V左/Width右。然后如果左侧位置还是Valley，那么重新令V左=Valley下一层的容积；如果左位置已经变成了Slope，那么继续向左侧找到新的Valley，令V左=新Valley最底层的容积。然后不断重复一开始的步骤直至V<=0。
上述思路可以做到O(n)复杂度, 其中n是直方图中bar的个数。在每次循环中，有两个关键步骤。1. 找最近的valley，2.填充valley的最低层。2是个O(1)操作，而1看似是O(n)操作，但是因为如果某次我们下降了k步才找到valley，那说明这个valley至少有k层。而整个直方图的总层数不会超过n（因为每一层都需要有一堵对应的墙），也就是说无论循环多少次，我们寻找valley的总步数并不会超过n步。综合来考虑，复杂度为O(n)。
代码见下，的这里直方图是用类似于LC上skyline的方法来表示的。即直方图中的每个bar由一个pair(left_x, height) 表示。比如[(1,2),(4,10),(5,0)]的意思是：“1~4之间高为2；4~5之间高为10；5以后均高为0”。另外，整个直方图是一个LinkedList，这样当某一个位置被填到和两侧一样高时，能够在O(1)时间内将其和两侧merge为一个新的位置。这是实现O(n)复杂度的关键。
这个长度的代码在面试时是很难完全写出的，所以这题我估计是思路为主，实现为辅。。
// Segment：直方图中的一个bar
// x: bar左侧的x坐标
// h: bar的高度
struct Segment {
int x;
double h;
Segment(int _x=0, double _h=0):x(_x), h(_h) {}
};
// mergeSegment：当iter位置处周围，高度相同的Segment合并为1个Segment
list<Segment>::iterator mergeSegment(list<Segment>::iterator iter, list<Segment>& level)
{
if (prev(iter)->h == iter ->h) {
iter = prev(iter); //
level.erase(next(iter)); //
}
if (next(iter)->h == iter->h) {
level.erase(next(iter));
}. From 1point 3acres bbs
return iter;
}
void getWaterLevel(list<Segment>& level, int pos, double amount)
{
// 左和右Valley的位置。
list<Segment>::iterator left, right;
// 找到pos在level中的对应位置。. From 1point 3acres bbs
for (auto iter = level.begin(); iter != level.end() && iter->x <= pos; ++iter)
left = iter;
right = left;
while (amount > 0)
{
while (prev(left)->h < left->h) --left; // 从left位置开始，向左找valley。
while (next(left)->h < left->h) ++left; // 如果left是个向右下倾斜的slope，那就向右找
while (next(right)->h < right->h) ++right; // 从right位置开始向右找Valley。
while (prev(right)->h < right->h) --right; // 如果right是个向左下倾斜的slope，那就向左找
int left_w = next(left)->x - left->x; // 两Valley的宽度
int right_w = next(right)->x - right->x;
double minleft_h = min(prev(left)->h, next(left)->h); // 两Valley最底下那一层的深度
double minright_h = min(prev(right)->h, next(right)->h);
double left_cap = left_w * (minleft_h - left->h); // 两Valley的容积
double right_cap = right_w * (minright_h - right->h);. From 1point 3acres bbs
double min_cap = min(left_cap, right_cap); // 两Valley中容积较小者
auto min_pit = (left_cap <= right_cap) ? left : right; // 两Valley中容积较小（大）者的位置
auto max_pit = (left_cap > right_cap) ? left : right;
if (left == right) { // 左和右Valley是同一个Valley时
if (amount < min_cap) { // 如果amount填不满当前层
left->h += amount / left_w; // 那么算出能填到的高度
amount = 0; // 就可以退出循环了
}
else {
left->h = minleft_h; // 否则，左Valley的高度会被填满
left = mergeSegment(left, level); // 然后将这个Valley和它左右两侧的Wall合并成一个位置（如果能的话）
amount -= min_cap; // 重新计算剩余水量
}
right = left; // 重新令right和left相等，因为left的值在mergeSegment时可能会变化
}
else { // 如果确实同时有两个Valley
if (amount < min_cap * 2) { // 那么amount的一半如果都不能填满较小的那个Valley，
left->h += (amount / 2) / left_w; // 那肯定更填不满较大的Valley。
right->h += (amount / 2) / right_w; // 因此两Valley都不会填满，只要重新计算两Valley高度
amount = 0; // 然后退出循环即可。
}
else if (amount >= min_cap * 2) { // 但是如果amount的一半能填满较小的Valley
amount -= min_cap * 2;
min_pit->h = min(prev(min_pit)->h, next(min_pit)->h); // 先算一下容积较小Valley的深度
if (left_cap <= right_cap) { // 如果是left较小的话
left->h = minleft_h; // 那么先填满left
left = mergeSegment(left, level);
right->h = min(right->h + min_cap / right_w, minright_h); // 然后再计算right处应该被填到的高度
// 这里如果right的容积==left容积的话，right也有可能被填满。
// 而且因为浮点数计算的关系，还有可能出现right的新高度稍大于其两侧墙的高度，
// 因此用一个min来强制其结果不超过墙的高度。
// 如果right也被填满了，就也需要把right和其两侧的墙merge成一个位置。
right = mergeSegment(right, level);
}
else { // 如果是right较小，则先merge right，再merge left。和上面刚好相反
right->h = minright_h;
right = mergeSegment(right, level);
left->h = min(left -> h + min_cap / left_w, minleft_h);
left = mergeSegment(left, level);. check 1point3acres for more.
}
}
}
}
}
我自己想了一个solution 貌似可以 求大家点评：
struct myData
{
int index;
int dist;
int height;
};
class Compare
{
public:
bool operator() (myData a, myData b)
{
return a.height > b.height || (a.height == b.height && a.dist > b.dist);. 1point3acres
}
};
void water(vector<int> heights, int amount, int pos)
{
int maxheight = 0;
priority_queue
<
myData,
vector<myData>,
Compare> minheap;
for (int i = 0; i < (int)heights.size(); i++)
{
maxheight = max(maxheight, heights[i]);
}
vector<vector<int>> map(maxheight, vector<int>(heights.size(), 0));
for (int j = 0; j < (int)heights.size(); j++)
{. check 1point3acres for more.
for (int i = 0; i < heights[j]; i++)
{
map[map.size()-i-1][j] = 1;
}
}
for (int i = 0; i < (int)map.size(); i++)
{
for (int j = 0; j < (int)heights.size(); j++). 1point3acres
{
cout << map[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n";
int leftindex = pos;
int rightindex = pos;
while(amount)
{
int lower = (leftindex == -1) ? maxheight + 1 : heights[leftindex];
lower = min(lower, (rightindex == (int)heights.size() ? maxheight + 1 : heights[rightindex]));
//cout << lower << "\n";
if (minheap.empty() || (lower < maxheight + 1 && minheap.top().height == lower))
{
while (rightindex < (int)heights.size())
{
if (minheap.empty() && rightindex == pos)
{
rightindex++;
continue;
}
minheap.emplace(myData{rightindex, abs(rightindex-pos), heights[rightindex]});
if (heights[rightindex] > heights[pos])
{
break;
}
rightindex++;
//cout << "right" <<rightindex << "\n";
}
while (leftindex >=0)
{
minheap.emplace(myData{leftindex, abs(leftindex-pos), heights[leftindex]});
if (heights[leftindex] > heights[pos])
{
break;
}
leftindex--;
//cout << "left" <<leftindex << "\n";
}
}
myData d = minheap.top();
minheap.pop();
if (d.height == maxheight) break;
//cout << "d.height" <<d.height << "\n";
//cout << "d.index" <<d.index << "\n";
map[map.size() - d.height -1][d.index] = 2;
d.height++;
heights[d.index]++;
minheap.emplace(d);
amount--;
for (int x = 0; x < (int)map.size(); x++). check 1point3acres for more.
{
for (int y = 0; y < (int)map[0].size(); y++)
{. check 1point3acres for more.
cout << map[x][y]<<" ";
}
cout<<"\n";
}
cout<<"\n";
}
for (int i = 0; i < (int)map.size(); i++)
{
for (int j = 0; j < (int)map[0].size(); j++)
{
cout << map[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n";
}
// To execute C++, please define "int main()"
int main() {
vector<int> heights = {5,4,2,1,2,3,2,1,0,1,2,4};
water(heights, 9, 5);
return 0;
}
这道题我至少看到过3次，但是都没有提到很好的solution，帮顶，坐等大神解答
帮顶，同想问下这道题
后来和别人讨论之后，想明白了，貌似只能brute force，一点一点的模拟。先假设一个flow preference，例如向左流，然后向左找到第一个index i, 满足water[i-1] > water[i]，如果没有找到，说明水都会流掉，存不下来。就可以结束。向左流满了之后，向右找。
想再问下，water 代表的是水的高度还是土地的高度？另外左右流的时候如何平均呢？谢谢
这个flow preference不能假设，只能根据实际直方图来决定，这也就是这题难的地方。比如这种情况：[10 8 6 4 2 1 3 5 7 9 7 5 7 11]. 9是一个local maximum，如果从这个位置倒水的话，水会均匀向两边的两个坑里流去。如果倒水的量比较少的话，水会均匀存在两个坑里，而不是会都存到左边。
那这样太难了，我觉得看大家分享的情况来看，最小单位就是一滴水，不用再均分了，如果左右，或者多个位置都一样高的话，就假设水都偏向一边，例如左面。
我没有表述清楚，还需要另外一个数组，存每一个index的水量。原来的数组不停的update，意思是土地+水的高度。我说的water,其实就是土+水的高度
大概明白了，谢谢。