单调栈题目

1 典型的单调栈问题，利用单调递减栈进行解决，从前和从后遍历都可以解决问题，从后遍历时，确定的是入栈元素的答案，从前遍历时，确定的是出栈元素的答案，

2 利用单调递减栈解决，关键是出栈时计算每个位置当前可以盛水的量，所以每次出栈后要保证栈不空，才可以计算盛水量，否则结束，

3 用单调递减栈从前往后遍历，多了一个用哈希表来记录映射，

4 单调递增栈，这个题的关键是求面积的方法，必须要前后加两个哨兵，注意面积的高为height[i]时，其宽必须是当前元素（将要入栈的元素）索引和栈中height[i]的前一个元素的索引的差减1，这里是关键，关键是求宽，栈中记录的是单调栈的索引，如栈是[2,3,6]，则说明height[4]，height[5]，height[6]中height[6]是最小的，所以其宽度为3，而height[3]小于height[6]

84. 柱状图中最大的矩形

5 腾讯逛街题，这个题实际上考虑的是单调递减栈中有多少个元素，不论将要入栈的元素是大于栈顶还是小于栈顶，其可以看到的楼的个数都是栈中的元素个数，所以先保存栈的元素个数，再进行压栈出栈操作，

# 自己的代码，用两个单调递减栈进行处理，一个顺序，一个倒序
l = int(input())
data = list(map(int, input().split()))
# l = 6
# data = [5,3,8,3,2,5]
res = [1] * l
stack = []
for i in range(l):
    k = len(stack)
    while stack and data[stack[-1]] <= data[i]:
        stack.pop()
    res[i] += k
    stack.append(i)
stack = []
for j in range(l-1, -1, -1):
    k = len(stack)
    while stack and data[stack[-1]] <= data[j]:
        stack.pop()
    res[j] += k
    stack.append(j)
str_res = ' '.join([str(i) for i in res])
print(str_res)
# for i in res:
#     print(i, end=' ')

View Code

https://www.nowcoder.com/question/next?pid=21283868&qid=830860&tid=32937832

递增递减指的是从栈底到栈顶

求解数组中元素右边第一个比它小的元素的下标，从前往后遍历，构造单调递增栈；
求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；
求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递减栈；
求解数组中元素左边第一个比它大的元素的下标，先构造单调递减栈。再从后往前遍历，这个题就是962. 最大宽度坡
链接：https://leetcode-cn.com/problems/maximum-width-ramp/solution/dan-diao-di-jian-zhan-on-by-
单调栈中的每个元素都可以看作是坡底（实际上并不一定严格在坡底，有可能在半山腰）的元素

参考：https://leetcode-cn.com/problems/maximum-width-ramp/solution/dan-diao-zhan-by-user8973/