高频面试题接雨水详解 - 单调栈

AC代码：

 public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> s = new Stack<>();

        for(int i = 0; i < height.length; i ++){
            while(!s.isEmpty() && height[s.peek()] < height[i]){
                int index = s.pop();

                if(s.isEmpty()) break;

                int left = s.peek();

                int min = Math.min(height[i],height[left]);
                ans += (min - height[index]) * (i - left - 1);           
            }
            s.push(i);
        }
        return ans;
    }

1. 题目分析

1.1 题目解析：

1.1.1为什么该题可以使用单调栈？

分析题意可知，只有当呈凹字状的才能接住雨水，所以在一系列的单调不增的数中，突然出现了一个数比前面的数大的话，我们就需要对前面的数进行结算。所以可以使用单调栈。

1.1.2 结算时的第一种情况

图中所标注的是下标，栈中存放的也是下标。且该种情况接不到雨水。

为什么在内层循环中需要设置以下代码？

if(s.isEmpty()) break;

当第一个元素的下标已经进栈，第二个的元素大于栈顶元素进入内层循环。栈对栈顶元素进行pop()，并且此时栈为空，我们需要对后面的代码进行终止。所以设置以上代码。

1.1.3 结算时的第二种情况

图中所标注的是下标，且该种情况下的所接雨水为4。

当程序运行到下图所示：

准备进栈的元素为下标为4的元素，此时它的值比栈顶元素的大。

执行以下代码：

int index = s.pop();

if(s.isEmpty()) break;

int left = s.peek();

int min = Math.min(height[i],height[left]);
ans += (min - height[index]) * (i - left - 1);           

此时的index为3，left为2，求出来的雨水量为1。

此时如下图所示：

如上图所示的栈中元素还要经过一次的对4的pop，因为求出的雨水量为0，所以此处省略。那么就是如上图所示了。

执行以下代码：

int index = s.pop();

if(s.isEmpty()) break;

int left = s.peek();

int min = Math.min(height[i],height[left]);
ans += (min - height[index]) * (i - left - 1);           

此时的index为2，left为1，求出来的雨水量为3。

所以此时的总雨水量为4。

2. 相关的模板总结

这里我们存入栈的是数组值，我们有时候还会将数组下标存入栈中哦。

2.1 单调递减栈 ： 求的是下一个更大的元素

for(int i = num.length - 1; i >= 0; i --){
   while(!s.isEmpty() && num[i] >= s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

2.2 单调递增栈 ： 求的是下一个更小的元素

for(int i = num.length - 1; i >= 0; i --){
    while(!s.isEmpty() && num[i] <= s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

2.3 维护的是一个单调递减栈

for(int i = 0; i < num.length; i ++){
    while(!s.isEmpty() && num[i] > s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

2.4 维护的是一个单调递增栈

for(int i = 0; i < num.length; i ++){
    while(!s.isEmpty() && num[i] > s.peek()){
        s.pop();
    }
    s.push(num[i]);
}

看到这里恭喜你离大厂有近一步。觉得有收获的话，留下你的三连!!!