🍕 单调栈

解决的问题： 求数组中每一个数字的两旁的距离最近的最大值。（最小值同理）

【单调栈】： 里面的元素一定是有序的，如果求取的是最大值，则栈底到栈顶方向是递减。

单调栈流程： 先假设数组中没有重复值

• 遍历每一个数字，判断该数字能不能进入栈中。 每当一个数字出栈时，就能够结算 —— 获取这个数字两边最近的最大值
• 如果要放入的数字小于栈顶元素 —— 能维持单调性，则将其压入
• 如果要放入的数字大于栈顶元素，则需要弹出某些元素
  • 弹出一个元素，它的左边最近最大值就是它弹出后的栈顶元素，它的右边最近最大值就是导致它弹出的数 —— 当前要放入的数字。
  • 也就是说，要放入的数字，是每一个弹出的元素的右边最大值，而弹出的元素的左边最大值，是它们弹出后的栈顶元素。
• 当遍历结束后，开始结束单调栈中剩余的元素
  • 遍历结束后才弹出的元素，说明他们的右边没有比它大的值了。
  • 而他们左边比它大的值，同样是弹出后的栈顶元素
  • 所以，最后弹出的元素，两边都没有最大值，因为它是整个数组的最大值。

没有重复值时，栈中每一个元素都只是一个数组中一个元素的下标。

• 当有重复值时，就是将栈中元素变成一个 “链表”，其他流程一样。
• 当要放入的元素和栈顶元素一样大时，直接放到该元素的链表后面。
• 当要弹出元素时，它的左边最大值，是栈顶元素的链表的最后一个元素。

【证明】:

• 假设现在要放入的元素是 c ，栈顶元素是 a ，元素 a 的的下一个值是 b

     <-- c
| a |  小
| b |  ↑
|...|  ↑
|___|  大

• 首先证明为什么 c 就是 a 的右边最大值
  • 首先， a...c 中间不可能有数字小于 a ，因为如果小于 a ，这个数字就入栈
  • 其次， a...c 中间不可能有数字大于 a ，如果这个数字大于 a ，那么 a 就会因为这个数字出栈了，而轮不到 c
• 再证明为什么 b 就是 a 的左侧最大值
  • 首先， b...a 中间数字有没有可能小于 a ，有可能！ 但这个数字一定会因为别人出栈了，不然就是当 a 进栈时这个数字就会出栈。
  • 其次， b...a 中间有没有可能大于 b ，不可能。因为大于 b 会将 b 弹出。
  • 最后， b...a 中间数字有没有可能大于 a 小于 10 ，不可能！
    • 假设 b 是 10 , a 是 7 ，中间数字是 8 ，如果没有数字将 8 弹出，那么 a 下面一定是 8 而不是 10。
    • 如果有数字将 8 弹出，该数字一定大于 8 ，假设是 9 ，那么，同理这个数字也一定会导致 a 和 b 之间有一个数字 9。
    • 如果又有数字比 9 大，那么这个数字会比 10 还大，那么 10 就不会留在栈中了。
    • 所以， b...a 中间不可能有数字大于 a 小于 10

【题目】定义:数组中累积和与最小值的乘积，假设叫做指标 A 。给定一个数组，请返回子数组中，指标 A 最大的值。

解释： 每一个数字都可以是某个多个数组的最小值，在这么多个数组，选取哪一个呢？ 选取累加和最大的那个数组。

解题敏感性： 这就是单调栈问题， 对每一个数字，都查找两边最近的最小值，这两个最小值围起来的区域就是以该数字为最小值所能够到达的最大区域，那么它的累加和肯定就是最大！