题解 | #接雨水问题#

接雨水问题

http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

双指针,但是更简单。

class Solution {
public:

	long long maxWater(vector<int>& arr) {
		// write code here
		int left = 1, right = arr.size() - 2;		//hole
		int h1 = arr[0], h2 = arr[arr.size() - 1];	//border
		int ans = 0;
		while (left <= right) {
			if (arr[left] >= h1) {	//h1 update
				h1 = arr[left];
				left++;
				continue;
			}
			if (arr[right] >= h2) {	//h2 update
				h2 = arr[right];
				right--;
				continue;
			}
			if (h1 < h2) {			//There exists water in left hole
				ans += h1 - arr[left];
				left++;
			}
			else{					//There exists water in right hole
				ans += h2 - arr[right];
				right--;
			}
		}
		return ans;
	}
};

再贴一个自测main函数:

int main() {
	ios::sync_with_stdio(0);	
	cin.tie(0);

//input
	string str;					
	stringstream ss;			
	getline(cin,str);
	ss << str;

//array initialise. separated by single space in a line. 
	int num;
	vector<int> arr;
	while (ss>>num) {
		arr.emplace_back(num);
	}

//water count
	Solution s;
	cout << s.maxWater(arr);
	return 0;
}

但这么简单的算法楞是想不到,把算法应用到具象问题的能力好重要哦。

----第二次编辑----

???'法'楞'是个什么和谐词,刚发出去的时候居然要标*** 我的知识又短浅了

全部评论

相关推荐

(黑话警告⚠️:hc=岗位数量,&nbsp;mt=导师,&nbsp;ld=直属领导,&nbsp;cr=代码审查)25年1月,我加入了字节某前端团队,并期望能在这里待到秋招并尝试转正。然而,就在上周,ld&nbsp;找我1v1,告诉我,我的能力和团队预期不太匹配,并和我劝退。晴天霹雳吗?肯定是有的。那一刻,脑子里嗡嗡作响,各种情绪翻涌。但冷静下来想想,这几个月,自己在能掌控的范围内,确实有不少地方做得不尽如人意。所以,我想把这段不算成功的经历复盘一下,希望能给同样在努力转正的你提个醒,避开我踩过的坑。一、ld&nbsp;的要求要注意刚进组时,ld就和我聊过转正的事。我当时发问:“咱们这儿有hc&nbsp;吗?”&nbsp;ld没直接回答,只是说:“看能力,能力到了...
牛客上的彭于晏:过来人告诉你,入职后要做的第一件事儿不是说主动找活儿做,你要先学会融入团队,摸清ld的性格,投其所好。然后才是展示你的能力,能力上可以说技术或者业务,以业务能力为主,技术能力为辅。优先保证自己对业务需求的开发保证质量效率,然后再谈技术的问题,不要你觉得啥啥啥不行就想着整体优化了(发现校招生最喜欢干这事儿),我工作快5年了发现搞这种的最后都没啥好的结果,产出没有还引入新的bug,校招或者实习的水平看到的问题别人看不到嘛?为什么别人不去搞?浪费时间还没收益的事儿不要去做,技术上的能力体现在对于一个新需求,在不符合现在业务发展的架构设计上,你能拿出好的技术方案同时能考虑到后续业务发展逐渐将技术架构引入合理的架构,这是一个漫长的过程而不是一次性的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务