栈讲解——整理

小灰灰 2021-03-28 14:30 356阅读 0赞

简单地说，栈是一种先进后出的数据结构，你可以把它想象成一个桶，每次只能从最顶端处放置或取出数据。

一般我们在io中用一个数组和栈顶指针（用int 便是下标）来模拟一个栈。

栈支持两个操作：

1.向栈顶加入一个元素

2。从栈顶取出一个元素。

这两个操作的时间复杂度都为o(1)

那么它所维护的这个数据集合中，数据之间有什么样的关系呢？

很简单，就是fisrt-in-last-out，或者更具体一点：如果一个元素在另一个元素之前加入这个集合中，那么它一定在那个元素之后退出这个集合。

单调栈

单调栈要求栈中的元素从栈底到栈顶是单调（有序）的，所以在加入一个新的元素时，如果它和栈顶元素不满足单调，那么将会依次弹出栈顶的元素直到这个元素加入到栈中依然满足单调，才将这个元素加入到栈中

例题：

## 题目描述 ##

Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

=       =

=   -   =         Cows facing right -->

=   =   =

= - = = =

= = = = = =

1 2 3 4 5 6 Cow\#1 can see the hairstyle of cows \#2, 3, 4

Cow\#2 can see no cow's hairstyle

Cow\#3 can see the hairstyle of cow \#4

Cow\#4 can see no cow's hairstyle

Cow\#5 can see the hairstyle of cow 6

Cow\#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

牛\#1 可以看到她们的发型 \#2, 3, 4  
牛\#2 不能看到任何牛的发型  
牛\#3 可以看到她的发型 \#4  
牛\#4 不能看到任何牛的发型  
牛\#5 可以看到她的发型 \#6  
牛\#6 不能看到任何牛的发型!  
让 c\[i\] 表示第i头牛可以看到发型的牛的数量；请输出 c\[1\] 至 c\[N\]的和。  
如上面的这个例子，正确解是3 + 0 + 1 + 0 + 1 + 0 = 5。

农民约翰的某N(1 < N < 80000)头奶牛正在过乱头发节！由于每头牛都意识到自己凌乱不堪 的发型，约翰希望统计出能够看到其他牛的头发的牛的数量.

每一头牛i有一个高度所有N头牛面向东方排成一排，牛N在最前面，而 牛1在最后面.第i头牛可以看到她前面的那些牛的头，只要那些牛的高度严格小于她的高度，而且 中间没有比hi高或相等的奶牛阻隔.

让N表示第i头牛可以看到发型的牛的数量；请输出Ci的总和

## 输入输出格式 ##

**输入格式：**

Line 1: The number of cows, N.

Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

**输出格式：**

Line 1: A single integer that is the sum of c1 through cN.

## 输入输出样例 ##

**输入样例\#1：**

6
    10
    3
    7
    4
    12
    2

思路：

维护一个单调递减的栈，每次当加入一个比他前面的数大的值时，是这个栈不满足单调递减的，那就把它前面比他小的元素弹出栈，让这个数入栈，当这个数被弹出时他所能看到的牛的头发的个数为新入栈的数减去弹出的数-1；

懂了？？

那就上代码！！

开long long 卡我9个点！！！！！

代码

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define maxn 1<<30
    #define N 80010
    using namespace std ;
    long long int stack[N],top,n,a[N];
    long long ans=0;
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
         cin>>a[i];//你也可以写成：scanf("%d",a+i);
        a[n+1]=maxn; 
        for(int i=1;i<=n+1;i++)//最后一头牛也要算入 
         {
             while(top&&a[stack[top]]<=a[i])//你是让这个元素的编号进栈 
             {
                 ans+=i-stack[top]-1;
                 top--;
              } 
              stack[++top]=i;
          } 
        cout<<ans;
        return 0;
    }