28190: 奶牛排队

http://cs101.openjudge.cn/practice/28190/

奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……

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

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

输入

第一行一个正整数 N，表示奶牛的头数。(2<=N<=10000)

接下来 N 行，每行一个正整数，从上到下表示从左到右奶牛的身高 hi (1<=hi<=50000000) 。

输出

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

样例输入

sample input1:
5
1
2
3
4
1

sample output1:
4

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

样例输出

sample input2:
10
15
15
2
13
7
4
11
5
11
12

sample output2:
5

提示

tags: monotonous-stack

来源

hhy, https://www.luogu.com.cn/problem/P6510

利用单调栈， left_bound用于记录以当前点为最右端，满足条件的最左端的索引减1； right_bound用于记录以当前节点为最左端，满足条件的最右端的索引加1，最终答案就是两段拼起来之后的最长长度。

python

"""
https://www.luogu.com.cn/problem/solution/P6510
简化题意：求一个区间，使得区间左端点最矮，区间右端点最高，且区间内不存在与两端相等高度的奶牛，输出这个区间的长度。
我们设左端点为 A ,右端点为 B
因为 A 是区间内最矮的，所以 [A.B]中，都比 A 高。所以只要 A 右侧第一个 ≤A的奶牛位于 B 的右侧，则 A 合法
同理，因为B是区间内最高的，所以 [A.B]中，都比 B 矮。所以只要 B 左侧第一个 ≥B 的奶牛位于 A的左侧，则 B合法
对于 “ 左/右侧第一个 ≥/≤ ” 我们可以使用单调栈维护。用单调栈预处理出 zz数组表示左，r 数组表示右。
然后枚举右端点 B寻找 A，更新 ans 即可。

这个算法的时间复杂度为 O(n)，其中 n 是奶牛的数量。
"""

N = int(input())
heights = [int(input()) for _ in range(N)]

left_bound = [-1] * N
right_bound = [N] * N

stack = []  # 单调栈，存储索引

# 求左侧第一个≥h[i]的奶牛位置
for i in range(N):
    while stack and heights[stack[-1]] < heights[i]:
        stack.pop()

    if stack:
        left_bound[i] = stack[-1]

    stack.append(i)

stack = []  # 清空栈以供寻找右边界使用

# 求右侧第一个≤h[i]的奶牛位
for i in range(N-1, -1, -1):
    while stack and heights[stack[-1]] > heights[i]:
        stack.pop()

    if stack:
        right_bound[i] = stack[-1]

    stack.append(i)

ans = 0

# for i in range(N-1, -1, -1):  # 从大到小枚举是个技巧
#     for j in range(left_bound[i] + 1, i):
#         if right_bound[j] > i:
#             ans = max(ans, i - j + 1)
#             break
#
#     if i <= ans:
#         break

for i in range(N):  # 枚举右端点 B寻找 A，更新 ans
    for j in range(left_bound[i] + 1, i):
        if right_bound[j] > i:
            ans = max(ans, i - j + 1)
            break
print(ans)

因为有单调栈的提示，所以优先思考单调栈的性质：能够找到（向左）一个最长的区间，其上面的值都比当前位置要小，于是当前位置就是这个区间的最大值——这算是想到了一半；

后一半就着重解决最左端最小值的性质，其实和前面是对称的想法，我要找到一个位置，这个位置必须要前面最长的区间内，且是区间最小值，这利用了单调栈中的另一个性质：单调栈内的元素，是单调的，意味着每个元素都是其到下一个元素之间的最小值——而最小值是具有传递性的，也就是每个元素是该位置当前遍历到的位置之间的最小值——恰好满足我们的要求。

于是我们只要找第一步中区间是否包含第二步中单调栈的元素即可（这里可以选择线性遍历或者二分，二分查找是因为单调栈是单调的），选择被包含元素中最左端的元素，就是以当前遍历到的位置为最大值的最长连续区间。

综上，我们只需要两个单调栈，一个是递增栈，一个是非增栈就好了。

python

# 熊江凯、元培学院
from bisect import bisect_right as bl
lis,q1,q2,ans=[int(input())for _ in range(int(input()))],[-1],[-1],0
for i in range(len(lis)):
    while len(q1)>1 and lis[q1[-1]]>=lis[i]:q1.pop()
    while len(q2)>1 and lis[q2[-1]]<lis[i]:q2.pop()
    id=bl(q1,q2[-1])
    if id<len(q1):ans=max(ans,i-q1[id]+1)
    q1.append(i)
    q2.append(i)
print(ans)

28190: 奶牛排队 ​

28190: 奶牛排队