单调栈

// 递增栈
for(int i=0; i<arr.length; i++) {
	while(!stack.empty() && stack.peek() >= arr[i]) {
		stack.pop();
	}
	stack.push(arr[i]);
}

// 递减栈
for(int i=0; i<arr.length; i++) {
	while(!stack.empty() && stack.peek() <= arr[i]) {
		stack.pop();
	}
	stack.push(arr[i]);
}

// 递减栈 栈中元素数目即为能看到的楼数目
// 两个栈 一个表示向左能看到的数目 一个表示向右 注意所有栈都不考虑当前所在楼本身 因此最后结果要加1
// 以向右看为例
// 单调栈里维护了从最左边到该位置前递减序列 而到达当前位置的递减序列对于当前位置来 都是可见的
// 因此单调栈的大小保存了能看到楼的个数

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Tencent2020backend2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] height = new int[n];
        for(int i=0; i<n; i++) {
            height[i] = sc.nextInt();
        }

        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ArrayList<Integer> count1 = new ArrayList<>();
        ArrayList<Integer> count2 = new ArrayList<>();

        for(int i = 0, j = height.length-1; i < height.length && j>=0; i++, j--) {
            count1.add(stack1.size());
            count2.add(0, stack2.size());
            while(!stack1.empty() && stack1.peek() <= height[i]) stack1.pop();
            while(!stack2.empty() && stack2.peek() <= height[j]) stack2.pop();
            stack1.push(height[i]);
            stack2.push(height[j]);
        }
        for(int i=0; i<n; i++) {
            System.out.print(count1.get(i) + count2.get(i) + 1 + " ");
        }
    }
}

# 递增栈
# 每次遇到非递增元素 可以计算一次面积 在所有计算的面积中找到最大的即可
# 巧妙的利用了递增栈的性质

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [-1]
        heights.append(-1)
        res = 0

        for idx, val in enumerate(heights):
            while heights[stack[-1]] > val:
                h = heights[stack.pop()]
                res = max(res, h*(idx - stack[-1]-1)) # idx-stack[-1]-1是当前递增序列的宽度
            stack.append(idx)
        return res