1.基本概述

单调栈是一种特殊的栈数据结构，其元素保持一定的单调性，通常是单调递增或单调递减。

与单调队列类似，单调栈也常用于解决一些与滑动窗口相关的问题，以及求解数组中每个元素的下一个更大元素等问题。

单调栈的工作原理：

• 首先，我们维护一个栈，栈中存放的是数组元素的索引。
• 对于数组中的每个元素，我们将其索引放入栈中，并且在放入栈之前，我们需要确保栈中的元素按照递减的顺序排列。这样，栈顶元素对应的数组元素就是当前元素的前一个更大元素。
• 当遍历到一个新的元素时，我们将其与栈顶元素比较，如果新元素比栈顶元素小，则将新元素的索引入栈。如果新元素比栈顶元素大，则将栈顶元素出栈，并且更新栈顶元素对应的数组元素的下一个更大元素为当前元素，并且重复此步骤直到栈为空或者新元素比栈顶元素小。

2.接雨水

代码：

package com.dreams.data;

import java.util.Deque;
import java.util.LinkedList;

class Solution {

    /*

    left     
     ___     ___
    |   |   |   |
    |   |___|   |

     */
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}

解释：

• 当栈不为空且当前元素的高度大于栈顶元素的高度时，说明可能存在一个水槽。
• 在这种情况下，持续弹出栈顶元素，直到栈为空或者当前元素的高度小于等于栈顶元素的高度。
• 对于每次弹出的栈顶元素，计算当前位置与上一个高度较小的位置之间的宽度，然后用较小的高度减去当前位置的高度，乘以宽度得到当前水槽的容量，将其累加到答案 ans 中。
• 将当前元素的索引压入栈中，继续循环直到遍历完整个数组。
• 最后返回计算出的答案 ans，即能够容纳的雨水量。

参考

黑马数据结构