牛客 小米校招 计算题 单调栈 接雨水

给定n个非负整数表示每个宽度为1的柱子的高度题,计算按此排列的柱子,下雨之后能接多少雨水。

经典的题目 leetcode 42 接雨水


单调栈

  • 保持栈内单调递减
  • 每次把一个矮的出栈都能够加上一大块面积

如下图

while(~scanf("%lld,", &m)) a[++n] = m;
stack<int> stk; //存下标
int sum = 0;
for(int i=1; i<=n; i++) {
	while(stk.size() && a[stk.top()] < a[i]) {
		int cur = stk.top();
		stk.pop();
		if(stk.empty()) break;
		int lef = stk.top(); //栈顶下标
		int rig = i; //当前i的下标
		int h = min(a[lef], a[rig]) - a[cur]; //求得高度
		sum += h * (rig - lef - 1);
	}
	stk.push(i);
}
printf("%lld\n", sum);

全部评论

相关推荐

强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 11:31
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务