成都市分类信息网站开发,博罗网站定制,广州定制网站设,最近国际重大新闻文章目录1. 题目2. 解题1. 题目
给出一个地形高度图#xff0c; heights[i] 表示该索引处的高度。 每个索引的宽度为 1。在 V 个单位的水落在索引 K 处以后#xff0c;每个索引位置有多少水#xff1f;
水最先会在索引 K 处下降并且落在该索引位置的最高地形或水面之上。然…
文章目录1. 题目2. 解题1. 题目
给出一个地形高度图 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:vectorint pourWater(vectorint 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[l1])//一样高靠近k处l;if(l ! K){heights[l];V--;continue;}r K;while(r n-2 heights[r] heights[r1])//右边有更低的r;while(r K heights[r-1] heights[r])r--;heights[r];//rK的情况合并了V--;}return heights;}
};4 ms 7.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
