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

x33g5p2x  于2021-11-21 转载在 其他  
字(1.7k)|赞(0)|评价(0)|浏览(407)

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);

此时的index3left2,求出来的雨水量为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);

此时的index2left1,求出来的雨水量为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]);
}

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

相关文章