学习资料：
[1] 数据结构系列/单调栈
[2] 单调栈原理及应用 详解 附各种类型的题目练习
[3] Leetcode 单调栈问题总结（超详细！！！）
[4] 数据结构——单调栈
单调栈的基本介绍见参考资料 [2].
单调栈的应用有下面2种基本情况：
1、给定一组数，针对每个数，寻找它和它右（左）边第一个比它大（小）的数之间有多少个数
2、给定一组数，针对每个数，寻找它右（左）边以最近的数字为最小值（最大值）的最长单调递增（递减）序列有多少个数
这两种情况的模板是类似的。
题型一
POJ 3250 牛的视野
资料 [1] 中有POJ 3250的参考答案，但是这篇博客对于POJ 3250描述不够准确，应该改为：
一群高度不完全相同的牛从左到右站成一排，每头牛只能看见它右边的比它矮的牛的发型，若遇到一头高度大于或等于它的牛，则无法继续看到这头牛后面的其他牛（即使它们也比它矮）。给出每头牛的身高，求每头牛能看到的牛的总数。
import sys
for n in sys.stdin:
n = int(n)
nums = [int(input().strip()) for _ in range(n)]
nums.append(float('inf')) # 在末尾添加一个无穷高的牛
stack = []
res = [0] * (n+1) # res[i] 表示第 i 头牛往右能看到多少头牛
for i in range(n, -1, -1):
while len(stack) > 0 and nums[i] >= nums[stack[-1]]:
stack.pop() # 把nums[i]右边比它矮的或一样高的出栈
# 此时如果栈非空，说明栈顶就是右边第一个比nums[i]高的牛。这之间牛的个数即为下标之差减一
res[i] = stack[-1] - i -1 if len(stack) > 0 else 0
stack.append(i)
# 如果问每一头牛能看到多少头牛，则返回res[:-1]。注意不需要最后一头无穷高的牛
# 但是本题问所有牛一共能看到多少头，所以求和。
print(sum(res[:-1]))
美团点评2020校招数据分析方向笔试题——比大小
分析：本题与上一题的不同之处在于：
1、如果一个数右边没有比它大的数，则不必记录差值，保留为-1即可。故不需要加一个无穷大。
2、根据题意，统计的是 stack[-1] - i 而不是 stack[-1] - i -1（因为要包括那个第一个比它高的数）
参考答案：
import sys
for n in sys.stdin:
n = int(n)
nums = [int(input().strip()) for _ in range(n)]
stack = []
res = [-1] * n
for i in range(n - 1, -1, -1): # 不需要加无穷大，从n-1而不是n开始倒序遍历
while len(stack) > 0 and nums[i] >= nums[stack[-1]]:
stack.pop()
res[i] = stack[-1] - i if len(stack) > 0 else -1 # 下标之差不需要减一
stack.append(i)
print('\n'.join([str(x) for x in res]))
环形排列
在上一题的基础上：如果这些数围成一个圈，求往顺时针方向看多少步才到达第一个比它高的（如果没有比它高的，则对应-1）。
思路：
增加了环形属性后，问题的难点在于：“下一个” 的意义不仅仅是当前元素的右边了，有可能出现在当前元素的左边。
解决思路为：将原始数组“翻倍”，就是在后面再接一个原始数组，这样的话，按照之前“比身高”的流程，每个元素不仅可以比较自己右边的元素，而且也可以和左边的元素比较了。
import sys
for n in sys.stdin:
n = int(n)
nums = [int(input().strip()) for _ in range(n)] * 2 # 再接一个一样的数组
stack = []
res = [-1] * 2 * n
for i in range(2 * n - 1, -1, -1): # n-1 修改为 2n-1
while len(stack) > 0 and nums[i] >= nums[stack[-1]]:
stack.pop()
res[i] = stack[-1] - i if len(stack) > 0 else -1
stack.append(i)
print('\n'.join([str(x) for x in res[:n]])) # 注意最后只需要前 n 个的结果
LC84. Largest Rectangle in Histogram
题目链接：84. 柱状图中最大的矩形
先逆序遍历，找到向右第一个比它矮的柱子，再顺序遍历，找到向左第一个比它矮的柱子，算出中间有多少柱子即为宽度，然后宽度乘以高即为面积。
如果左边或右边没有比它矮的柱子，就没办法求出它们中间有多少比它高（或一样高）的柱子，所以类似于“POJ 3250 牛的视野”，此处需要分别在开头和末尾插入一个最矮的数0。
class Solution:
def largestRectangleArea(self, heights) -> int:
n = len(heights)
if n==0:return 0
# 开头和末尾都要插入一个最矮的数
heights.insert(0, 0)
heights.append(0)
stack = []
right_look = [0] * (n + 2)
for i in range(n + 1, -1, -1):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
stack.pop()
right_look[i] = stack[-1] - i - 1 if len(stack) > 0 else 0
stack.append(i)
stack.clear()
res = [x for x in right_look]
for i in range(n + 2):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
stack.pop()
res[i] += (i - stack[-1] - 1 if len(stack) > 0 else 0) + 1 # 先求出矩形的宽度（往左+往右+自己）
res[i] *= heights[i] # 宽度乘以高
stack.append(i)
return max(res[1:-1]) # 去掉加入的开头和末尾的0对应的值
求最大区间
题目来自文章开头写的参考资料 [3]
本题与上一题LC84类似，但要注意区间的范围如何用切片来表达。
class Solution:
def largestRectangleArea(self, heights) -> int:
n = len(heights)
heights.insert(0, 0)
heights.append(0)
stack = []
right_look = [0] * (n + 2)
for i in range(n + 1, -1, -1):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
stack.pop()
# 区间 [i+1, stack[-1]-1] 的和，即不包括柱子i和柱子stack[-1]
right_look[i] = sum(heights[i + 1:stack[-1]]) if len(stack) > 0 else 0
stack.append(i)
stack.clear()
res = [x for x in right_look]
for i in range(n + 2):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
stack.pop()
# 区间 [stack[-1]+1, i-1] 的和，即不包括柱子i和柱子stack[-1]
res[i] += (sum(heights[stack[-1] + 1:i]) if len(stack) > 0 else 0) + heights[i] # 先求出总区间的和（注意加上柱子i）
res[i] *= heights[i] # 区间的和乘以最小值
stack.append(i)
return max(res[1:-1])
题型二
腾讯2020校园招聘编程题——逛街
注意，题型一的栈中需要保存下标，因为需要在出栈时通过下标相减来得到距离
而在题型二，栈中没必要保存下标，因为每个位置对应的结果是 栈的元素个数 而不是 栈顶元素与当前元素的位置差值。
import sys
# 本答案参考自评论区
def parse_nums(nums_str):
return [int(x) for x in nums_str.strip().split()]
for n in sys.stdin:
n = int(n)
nums = parse_nums(input())
assert n == len(nums)
right_look = [0] * n
stack = []
# 从右往左遍历，统计每个位置往右看能看到多少栋楼（往右的高度单调递增）
# 注意对比题型一，记录结果的语句提到了while前，且记录的是栈的元素个数
for i in range(n - 1, -1, -1):
right_look[i] = len(stack) # 此时栈中的元素个数即为右边最长的单调递增序列的长度
while len(stack) != 0 and nums[i] >= nums[stack[-1]]:
stack.pop()
stack.append(i)
stack.clear()
# 从左往右遍历，统计每个位置往左看能看到多少栋楼（往左的高度单调递增）
both_look = [x for x in right_look]
for i in range(n):
both_look[i] += len(stack)+1 # 能看到楼的总数为往右+往左+自己
while len(stack) != 0 and nums[i] >= nums[stack[-1]]:
stack.pop()
stack.append(i)
both_look = [str(x) for x in both_look]
print(' '.join(both_look))
转载：https://blog.csdn.net/xpy870663266/article/details/104935930