栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的应用

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

P1153乱头发节

题目描述

李智宇的某 N 头奶牛 (1 <= N <= 80,000) 正在过乱头发节！由于每头牛都 意识到自己凌乱不堪的发型， 宁智贤希望统计出能够看到其他牛的头发的牛的数量。 每一头牛 i有一个高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向东方排成 一排(在我们的图中是向右)。因此，第i头牛可以看到她前面的那些牛的头， （即i+1, i+2,等等），只要那些牛的高度严格小于她的高度。

-牛#1 可以看到她们的发型 2, 3, 4

-牛#2 不能看到任何牛的发型

-牛#3 可以看到她的发型 4

-牛#4 不能看到任何牛的发型

-牛#5 可以看到她的发型 6

-牛#6 不能看到任何牛的发型!

输入：

  • Line 1: 牛的数量 N。
  • Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。

输出：

  • Line 1: 一个整数表示c[1] 至 c[N]的和.

题解：

看到这道题，你是不是想到了神奇的枚举吗？一个二重循环，完美AC！！！等等，二重循环？O（n^2）? 80000数据？

是的，要超时。( 简直就是废话！）

所以就需要用到一个超级高效的算法了，那就是利用单调栈！

我们将元素单调存入栈中，如果当前元素大于等于栈顶，那么栈顶出栈，统计栈顶看到有多少头牛。如果栈为空，或当前元素比栈顶小，当前元素进栈。所以说，这个算法由于每个元素只会进入一次和出一次，所以是O（n）的。

至于怎么统计有多少头牛，你只需要看栈顶牛的位置和当前比栈顶大的牛的位置相差的数值减去看不到的当前牛就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[80001]={0},b[80001],top=0,n,in;
long long ans=0;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++)
    {
		if(b[i]>=b[a[top]]&&a[top]!=0)
        {
            ans+=i-a[top]-1;
            a[top]=0;
            top--;
            i--;
        }
        else if(a[top]==0||b[i]<b[a[top]])
        {
            a[++top]=i;
        }
    }
    while(top>0)
    {
        ans+=n-a[top];
        top--;
    }
    cout<<ans<<endl;
    return 0;
}