单调栈基础：奶牛排队

单调栈

引入

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

过程

插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 0,11,45,81。

插入元素 14时为了保证单调性需要依次弹出元素 0,11，操作后栈变为 !14,45,81。

用伪代码描述如下：

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

实现

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

使用

可以用于从乱序数组某一元素出发，向左可以找到第一个小于他的数，或者第一个大于他的数，向右可以找到第一个小于他，或者大于他的数字（大于等于，小于等于也可以实现），而且能实现对每一个数组中元素，都找到对应的第一个大于他or小于他的数字，由此生成一个新数组。

以下为经典的奶牛排队问题

[USACO09MAR] Look Up S

题目描述

约翰的 $N(1\le N\le10^5)$ 头奶牛站成一排，奶牛 $i$ 的身高是 $H_i(1\le H_i\le10^6)$。现在，每只奶牛都在向右看齐。对于奶牛 $i$，如果奶牛 $j$ 满足 $i<j$ 且 $H_i<H_j$，我们可以说奶牛 $i$ 可以仰望奶牛 $j$。 求出每只奶牛离她最近的仰望对象。

Input

输入格式

第 $1$ 行输入 $N$，之后每行输入一个身高 $H_i$。

输出格式

共 $N$ 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 $0$。

样例 #1

样例输入 #1

6 
3 
2 
6 
1 
1 
2

样例输出 #1

3 
3 
0 
6 
6 
0

提示

【输入说明】$6$ 头奶牛的身高分别为 3,2,6,1,1,2。

【输出说明】奶牛 #1,#2 仰望奶牛 #3，奶牛 #4,#5 仰望奶牛 #6，奶牛 #3 和 #6 没有仰望对象。

【数据规模】

对于 $20\%$ 的数据：$1\le N\le10$；

对于 $50\%$ 的数据：$1\le N\le10^3$；

对于 $100\%$ 的数据：$1\le N\le10^5,1\le H_i\le10^6$。

用单调栈完成：

#include<iostream>
#include<stack>
using namespace std;
typedef struct 
{
    long long number,watch,height;
}cow;
int main()
{
    int n;
    stack<cow> st;
    cin>>n;
    cow a[n];
    for (int i=0;i<n;i++)
    {
        cin>>a[i].height ;
        a[i].number =i+1;
    }
    for (int i=0;i<n;i++)
    {
        while(!st.empty() && st.top().height<a[i].height )
        {//奶牛按照身高进入单调栈，栈底小，栈顶大
            a[st.top().number-1].watch =a[i].number ;
//被pop出单调栈的奶牛意味着他的右侧最近的比他大的奶牛是a【i】可以将他的箭头指向那个元素
            st.pop();
        }
        st.push(a[i]);
    }
    while(!st.empty() )
        {
            a[st.top().number-1].watch =0;
            st.pop();//剩下没出栈的奶牛的右边都没有比他高的奶牛了，根据题意，赋值为0；
        }
    for (int i=0;i<n;i++)
        {
            cout<<a[i].watch <<endl;
        }
    return 0;

}

注意，这里的关键是我去遍历到a[i]时候，所确定的不是a[i]仰望的奶牛，而是仰望a[i]的奶牛，a[i]是”被看“的奶牛！

奶牛排队

题目描述

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 $A$ 是最矮的，最右边的 $B$ 是最高的，且 $B$ 高于 $A$ 奶牛。中间如果存在奶牛，则身高不能和 $A,B$ 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 $0,2$，但不会是 $1$）。

输入格式

第一行一个正整数 $N$，表示奶牛的头数。

接下来 $N$ 行，每行一个正整数，从上到下表示从左到右奶牛的身高 $h_i$。

输出格式

一行一个整数，表示最多奶牛数。

样例 #1

样例输入 #1

5
1
2
3
4
1

样例输出 #1

4

提示

样例解释

取第 $1$ 头到第 $4$ 头奶牛，满足条件且为最多。

数据范围

对于全部的数据，满足 $2 \le N \le 10^5$，$1 \le h_i <2^{31}$。

题中的“左边最矮”“右边最高”等信息让我们考虑使用单调栈来快速处理。

首先用单调栈处理出每头奶牛左边第一个身高大于等于它的奶牛位置+1的位置（watchlefthigh元素）以及右边第一个身高小于等于它的奶牛位置−1的位置（watchrightlow元素）。为什么呢？这样做，我们就框定了每头奶牛分别作为合题奶牛组的左端点A和右端点B时，剩余的端点B，A可取的范围。

#include<iostream>
#include<stack>
using namespace std;
typedef struct 
{
    long long number,watchrightlow,height,watchlefthigh;
}cow;
int main()
{
    int n,max=0;
    stack<cow> st;
    scanf("%d",&n);
    cow a[n];
       //输入部分
    for (int i=0;i<n;i++)
    {
        scanf("%ld",&a[i].height);
        a[i].number =i;
    }

    //第一次单调栈
    for (int i=0;i<n;i++)
    {
        while(!st.empty() && st.top().height>=a[i].height )
        {
            a[st.top().number].watchrightlow =a[i].number-1 ;
            st.pop();
        }
        st.push(a[i]);
    }
    while(!st.empty() )
        {
            a[st.top().number].watchrightlow =n-1;
            st.pop();
        }

//第二次单调栈
    for (int i=n-1;i>=0;i--)
    {
        while(!st.empty() && st.top().height<=a[i].height )
        {
            a[st.top().number].watchlefthigh =a[i].number+1 ;
            st.pop();
        }
        st.push(a[i]);
    }
    while(!st.empty() )
        {
            a[st.top().number].watchlefthigh =0;
            st.pop();
        }
//检索重合区域
    for(int i=n-1;i>=0;i--)
    {
        for (int j=i;j>=a[i].watchlefthigh ;j--)
        {
            if(a[j].watchrightlow >=i)
            {

                max=max>i-j+1?max:i-j+1;
            }
         } 
    }
    if(max==1)max=0;
//处理特殊情况（题意）
    cout<<max<<endl;
    return 0;

}