单调栈热门博客列表 - ITeye博客频道

博客专栏推荐

本月博客排行

年度博客排行

单调栈的一些应用

1、何为单调栈：顾名思义，栈中的元素是按照某种方式排列，但是必须是单调的，如果某元素破坏了栈的单调性，就弹出栈的元素，直到该元素满足栈的单调性为止。 2、用途：可以很方便的求出某元素左边或右边第一个比其大或者小的元素，且时间复杂度O（n）; hm 与 zx系列故事题目链接训练赛的时候没能够做出来，自己当时根本就不知到什么是单调栈，更别说应用了，平时应该多多的积累一些知识点，遇到不会 ...

单调栈 hm 与 zx 的故事系列

ren_hui 评论(0) 有1992人浏览 2013-12-01 22:09

[单调栈]poj 3250：Bad Hair Day

大致题意：一排共n头牛排队站在一起，给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。大致思路：做到poj3415，居然碰到“单调栈”这种牛逼的玩意，于是专门来把这道题切掉。所谓单调栈也就是每次加入一个新元素时，把栈中小于等于这个值的元素弹出。接下来回到这道题。求所有牛功能看到多少牛，可以转化为：这n头牛共能被多少头牛看见。 ...