Leetcode@Pouring Water

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.

Otherwise, if the droplet would eventually fall by moving right, then move right.

Otherwise, rise at it's current position.

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.

Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    <- index

The first drop of water lands at index K = 3:

#       #
#   w   #
##  # ###
#########
 0123456    

When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)

#       #
#       #
## w# ###
#########
 0123456    

Since moving left will not make it fall, it stays in place.  The next droplet falls:

#       #
#   w   #
## w# ###
#########
 0123456  

Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)

#       #
#  w    #
## w# ###
#########
 0123456  

#       #
#       #
##ww# ###
#########
 0123456  

After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.

#       #
#   w   #
##ww# ###
#########
 0123456  

#       #
#       #
##ww#w###
#########
 0123456  

Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:

#       #
#   w   #
##ww#w###
#########
 0123456  

The final answer is [2,2,2,3,2,2,2]:

    #    
 ####### 
 ####### 
 0123456 

Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.

Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]

Note:

1. heights will have length in [1, 100] and contain integers in [0, 99].
2. V will be in range [0, 2000].
3. K will be in range [0, heights.length - 1].

这道题并不难，但是就是题目的条件要处理好，有些tricky。

基本思路是： 

       1. 当一滴水落下，对比左右两边的情况，判断水应该往哪一边流动。因为题目规定是check left first, then right，那么先判断左边，cur > 0 && heights[cur-1] <= heights[cur], 这里为什么 <= 是很有讲究，允许水滴往左边走在当前和左边高度一致的情况下，因为左边有可能有洼地。

      2. 随后判断右边，cur < n-1 && heights[cur+1] <= heights[cur], 此时同时也是 <=， 为什么呢？因为若水滴一直流向左边，最后发现没有洼地，也就是说左边一排的高度是一致的，此时也要允许流往右边，来看看右边有洼地的可能性。

     3. 第三个while loop很讲究，因为有可能左边和右边以及当前点，都是平齐的，按照题意，就让水滴落在当前地方，所以呢，因为之前往右走了很多，所以这里check while(cur > K && heights[cur-1] <= heights[cur]) cur--，这个while会被运行到的唯一情况就是左右都是平的，不然水已经落到某个洼地了，此处不会被执行，这个语句的意思就是回到K来。

    4. 最后heights[cur]++

Follow up: 如果两边不是高墙，而是洼地怎么办？也就是水如果能到边界，就会都流出去。加一个判断

if (cur == 0 || cur == n-1) continue; 如果cur能够到达0 or n-1，那么水注定就会要流掉，height不变，可以直接返回，因为下面一颗水滴也会流走。

class Solution {
    int n;
public:
    vector<int> pourWater(vector<int>& heights, int V, int K) {
        n = heights.size();
        for (int i = 0; i<V; i++)
        {
            int cur = K;
            while(cur > 0 && heights[cur-1] <= heights[cur]) cur--;
            while(cur < n-1 && heights[cur+1] <= heights[cur]) cur++;
            while(cur > K && heights[cur-1] <= heights[cur]) cur--;
            heights[cur]++;
        }
        return heights;
    }
};