单调栈.md

单调栈

数组中任意一个元素的左边和右边离它最近的比它小（大）的数，且时间复杂度O（N）

Code_0088_MonoStack.java

子数组累加和乘以子数组最小值所得到的结果最大是多少

Code_0089_AllTimesMinToMax.java

直方图最大矩形的面积

LeetCode_0084_LargestRectangleInHistogram.java

找出只包含1的最大矩形的面积

LeetCode_0085_MaximalRectangle.java

统计全1子矩形个数

LeetCode_1504_CountSubMatricesWithAllOnes.java

子数组的最小值之和

LeetCode_0907_SumOfSubarrayMinimums.java

单调栈 可以用来解决最大仰角问题

---

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。 山峰A和山峰B能够相互看见的条件为:

1.如果A和B是同一座山，认为不能相互看见。

2.如果A和B是不同的山，并且在环中相邻，认为可以相互看见。

3.如果A和B是不同的山，并且在环中不相邻，假设两座山高度的最小值为min。

1)如果A通过顺时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见

2)如果A通过逆时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见

3)两个方向只要有一个能看见，就算A和B可以相互看见 给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。

进阶: 给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。

tips:

无重复值

可以打表

除去最大值，次大值，其余的数都可以找到两对 2 * (N - 2) + 1

NowCoder_ViewMountain

有重复值 包装一个（值，次数）的对象 单调栈 循环遍历 栈由小到大 弹出就结算

注意清算的时候，计算逻辑 最大值的结算 NowCoder_ViewMountainNoRepeat

扩展 Leetcode 845 最长山脉问题 【单调栈】