给出一个地形高度图, heights[i] 表示该索引处的高度。 每个索引的宽度为 1。在 V 个单位的水落在索引 K 处以后,每个索引位置有多少水?
水最先会在索引 K 处下降并且落在该索引位置的最高地形或水面之上。然后按如下方式流动:
我们可以假定在数组两侧的边界外有无限高的地形。而且,不能有部分水在多于 1 个的网格块上均匀分布 - 每个单位的水必须要位于一个块中。
示例 1:
输入:heights = [2,1,1,2,1,2,2], V = 4, K = 3
输出:[2,2,2,3,2,2,2]
解释:
# #
# #
## # ###
#########
0123456 <- 索引
第一个水滴降落在索引 K = 3 上:
# #
# w #
## # ###
#########
0123456
当向左或向右移动时,水可以移动到相同或更低的高度。When moving left or right, the water can only move to the same level or a lower level.
(从水平上看,意思是该列的地形高度加上水的高度)
由于向左移动可以最终下落,因此向左移动。
(一个水滴 “下落” 的意思是可以相比之前可以进入更低的高度)
# #
# #
## w# ###
#########
0123456
由于向左移动不会使其降落,所以停在该位置上。下一个水滴下落:
# #
# w #
## w# ###
#########
0123456
由于新水滴向左移动可以最终下落,因此向左移动。
注意水滴仍然是优先选择向左移动,
尽管可以向右移动(而且向右移动可以下落更快)
# #
# w #
## w# ###
#########
0123456
# #
# #
##ww# ###
#########
0123456
经过刚才的阶段后,第三个水滴下落。
由于向左移动不会最终下落,因此尝试向右移动。
由于向右移动可以最终下落,因此向右移动。
# #
# w #
##ww# ###
#########
0123456
# #
# #
##ww#w###
#########
0123456
最终,第四个水滴下落。
由于向左移动不会最终下落,因此尝试向右移动。
由于向右移动不会最终下落,因此停在当前位置:
# #
# w #
##ww#w###
#########
0123456
最终的答案为 [2,2,2,3,2,2,2]:
#
#######
#######
0123456
示例 2:
输入:heights = [1,2,3,4], V = 2, K = 2
输出:[2,3,3,4]
解释:
最后的水滴落在索引 1 位置,因为继续向左移动不会使其下降到更低的高度。
示例 3:
输入:heights = [3,1,3], V = 5, K = 1
输出:[4,4,4]
注:
heights 的长度为 [1, 100] ,并且每个数的范围为[0, 99]。
V 的范围 [0, 2000]。
K 的范围 [0, heights.length - 1]。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/pour-water 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<int> pourWater(vector<int>& heights, int V, int K) {
int l = K, r = K, n = heights.size();
while(V)//还有水
{
l = K;
while(l >= 1 && heights[l-1] <= heights[l])//左边有更低的
l--;
while(l < K && heights[l] == heights[l+1])//一样高,靠近k处
l++;
if(l != K)
{
heights[l]++;
V--;
continue;
}
r = K;
while(r <= n-2 && heights[r] >= heights[r+1])//右边有更低的
r++;
while(r > K && heights[r-1] == heights[r])
r--;
heights[r]++;//r==K的情况合并了
V--;
}
return heights;
}
};
4 ms 7.2 MB