木板灌水问题(单调栈)

灰太狼 2022-05-12 10:46 217阅读 0赞

题意:地上从左到右竖立着N块木板,从1到n依次编号,如下图所示。我们知道每块木板的高度,在第n块模板右侧竖立着一块高度无限大的木板,现在对每块木板依次执行如下操作:对于第i块木板,我们从其右侧开始倒水,直到水的高度等于第i块木板的高度,倒入的水淹没ai块木板(如果木板左右两侧水的高度大于等于木板高度即可视为木板被淹没)。求n次操作后,所有ai的和为多少。

![70][]

解决思路:

什么时候谁的高度会等于第i块木板的高度hi呢?当水向右边漫延遇到了一块高度大于等于hi的木板j,ai就等于木板i和木板j之间的木板数,所以我们可以利用单调栈来解决:插入时,判断栈顶是否比它大,如果比它小,将ai+1,如果比它大,则正常入栈

算法如下:

#include <iostream>
    #include <stack>
    using namespace std;
    
    class Node {
    public:
    	int id;
    	int height;
    };
    
    int main() {
    
    	int n = 0;
    	cin >> n;
    	stack<Node> monotonousStack;
    	Node temp;
    	int sum = 0;  //用来计算最后的和
    	for (int i = 0; i < 5; ++i) {
    		temp.id = i;
    		cin >> temp.height;
    		while (!monotonousStack.empty() && temp.height >= monotonousStack.top().height) {
    			sum += i - (monotonousStack.top().id - 1);  
    			monotonousStack.pop();
    		}
    		monotonousStack.push(temp);
    	}
    	while (!monotonousStack.empty()) {
    		sum += n + 1 - (monotonousStack.top().id - 1);
    	}
    	
    	cout << sum << endl;
    	system("PAUSE");
    	return 0;
    }

[70]: /images/20220512/23523ec8d3f44ab98c186de04919df72.png

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】单调栈问题

文章目录题目思路分析代码实现题目给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr\[i\]小的位置

冷不防/ 2024年03月16日 09:55/ 0 赞/ 72 阅读

相关单调栈

> 参考https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaru

叁歲伎倆/ 2022年12月12日 13:58/ 0 赞/ 191 阅读

相关单调栈，栈还能单调一下？

之前遇到一个算法题目，自己只会用时间复杂度 O(N^2) 暴力解法解决，有大佬说用单调栈，可以做到 O(N) 的时间复杂度，当时我的表情是这样的： ![1d3f60a4338

水深无声/ 2022年09月12日 11:59/ 0 赞/ 215 阅读

相关单调栈 - AcWing 830. 单调栈（C++）- 简单

题目链接：[https://www.acwing.com/problem/content/description/832/][https_www.acwing.com_prob

喜欢ヅ旅行/ 2022年08月28日 01:46/ 0 赞/ 238 阅读

相关 node.js之评论灌水

> 内容来源慕课网 let http = require('https') let querystring = require('querystring')

港控/mmm°/ 2022年05月27日 12:13/ 0 赞/ 174 阅读

相关木板灌水问题(单调栈)

题意:地上从左到右竖立着N块木板,从1到n依次编号,如下图所示。我们知道每块木板的高度,在第n块模板右侧竖立着一块高度无限大的木板,现在对每块木板依次执行如下操作:对于第i块木

灰太狼/ 2022年05月12日 10:46/ 0 赞/ 218 阅读

相关单调栈

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。单调栈性质： 1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素

ゝ一纸荒年。/ 2022年05月12日 07:28/ 0 赞/ 261 阅读

相关日常灌水开发经验贴

学而不思则罔。突然意识到为什么觉得自己写的代码垃圾了，或者总有种隐隐不对劲的感觉。一：好的编程书写习惯 1. 合乎常规团队话的命名方式 2. 名字含义明确的函数命名方

男娘i/ 2021年12月14日 13:01/ 0 赞/ 279 阅读

相关单调栈

单调栈性质单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。模型例如下图就是一个单调递增的单调栈。 ![

你的名字/ 2021年11月10日 12:46/ 0 赞/ 321 阅读

相关单调栈

一、单调栈定义单调递增栈：数据出栈的序列为单调递增序列（比站内元素小就入栈，否则将栈中比当前元素小的元素弹出后再入栈）单调递减栈：数据出栈的序列为单调递减

水深无声/ 2021年09月21日 05:40/ 0 赞/ 435 阅读