【免费】RE_栈1资源-CSDN文库

需积分: 0 103 浏览量 2022-08-03 22:18:01 上传评论收藏 217KB PDF 举报

资源详情

资源评论

资源推荐

RE_栈.md

2021/6/22

1 / 4

Q22 : 括号生成 N对括号：可以生成不同的有效括号种类数。种类数，一

般都是回溯，才能查到所有情况了。

1. 任何时候，左括号个数，必须大于等于右括号个数。即是合法的。所以可以用回溯法。并设定left <

right 的条件。

2. 每一层可以加一个括号。可以加左，也可以加右，加右要满足left < right

3. 直到 left = 0,right = 0，结束。

Q84 : 柱状图中最大的矩形重点

1. 存下标的单调栈枚举矩形的高度

2. 思想：关于这种数组中找最大矩形，的题。可以明确的是，矩形的高，一定是数组中某元素的值。

3. 所以：只要我们枚举每一个元素作为高，求其最大宽度即可。

4. 所以：这题中，当我们读到一个元素，他小于之前的元素，那么之前的元素作为高的矩形就一定已经

确定了。因为水桶效应。

5. 若nums[i] < nums[stack[top]] 那么以stack[top]为左边界的矩形就确定了，说明 stack[top] 到 i之间的元

素都大于nums[stack[top]]，否则stack[top]一定会出栈。

假设有 23547 当i到4的时候栈中是235，发现比5低，那么以5作为高的矩形就确定了。

所以栈中变为 234

假设有 235647 当i到4的时候栈中是2356，发现比6低，那么以6作为高的矩形就是他本

身。然后栈变为 235， 4<5,那么以5作为高的矩形也确定了。他的右侧边界就是 i-1.也就

是6的位置。56组成以5作为高的矩形。

假设有 212...后序都大于2 当遇到1的是偶栈中是 2， 1<2 那么以2作为高的矩形就是

他本身。然后栈变为1， 2再入栈。.。。。

最终假设栈中只保留了 12 那么以2作为高的矩形的右侧边界就是数组边界，因为数组右侧

都大于2。

还有一个题也是类似：即可以装数组元素作为边沿，找最大矩形可以装多少水。也是枚举水

桶边。让每一个元素作为边，找最大宽度。

Q85 : 最大矩形 : 01矩阵中：由1填充的最大矩形。

1. 乍一看是动态规划

2. 其实是单调栈。而且就是Q84的变行

3. 把第一行作为初试高度heights[] ,然后求若只有第一行的最大矩形。

4. 然后第二行，若第二行是1，那么该列的高度就可以加1. 若是0，那么该列的高度就改为0. 每次都通过

Q84题来求解heights的最大矩形。

5. 然后每加入一行，就更新一次heights[]的高度。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

内容反馈

赵伊辰

粉丝: 57
资源: 314

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip