接雨水
大约 4 分钟
接雨水
单调栈
首先介绍一下单调栈结构：
单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。
单调递减栈
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。
单调递增栈
单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的。
题目分析
使用单调递减的栈结构：
- 遇到元素就先入栈。
- 然后每次入栈元素，就比较和栈顶索引对应的元素的值的大小。
- 如果大于栈顶索引所对应的元素值，那么就说明有高度差，可以进行计算。
- 注意，这个时候，栈里面可能存在多个元素，所以我们需要使用whiel进行循环判断栈中的元素，直到栈顶的元素不在小于当前的元素即可。
- 然后将当前的元素入栈即可。
代码实现
go实现
func trap(height []int) int {
/*创建一个栈结构,栈的长度时0，可以动态变化*/
stack := make([]int, 0)
/*面积总和*/
var sum int
/*循环遍历数组*/
for i := 0; i < len(height); i++ {
/*单调递减的栈结构*/
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
/*首先抛出栈顶元素*/
mid := stack[len(stack)-1]
/*使用切片方法模拟抛出栈顶元素*/
stack = stack[:len(stack)-1]
/*判断栈是否空*/
if len(stack) == 0 {
break
}
/*抛出左侧元素*/
left := stack[len(stack)-1]
//stack = stack[:len(stack)-1]
/*计算面积*/
min := min(height[i], height[left])
sum += (min - height[mid]) * (i - left - 1)
}
/*如果满足单调栈，就直接入栈元素*/
stack = append(stack, i)
}
return sum
}go语言中没有标准的数据结构api，因此像栈，队列这种结构需要我们使用数组实现;
首先使用数据声明一个栈结构
stack := make([]int, 0)抛出栈元素
mid := stack[len(stack)-1]
使用切片将栈长度减小
stack = stack[:len(stack)-1]入栈一个元素
stack = append(stack, i)java实现
class Solution {
public int trap(int[] height) {
return trap_A(height);
}
public int trap_A(int []height){
// 使用单调栈结构
int sz = height.length;
int sum = 0;
Stack<Integer> minStack = new Stack();
for(int i=0;i<sz;i++){
while(!minStack.isEmpty() && height[i]>height[minStack.peek()]){
// 从栈中抛出元素，计算
int index = minStack.pop();
if(minStack.isEmpty()){
break;
}
// 计算左侧边界
int left =minStack.peek();
// 计算高度
int min = Math.min(height[i],height[left]);
// 计算面积
sum +=(min-height[index])*(i-left-1);
}
minStack.push(i);
}
return sum;
}
}时间复杂度：o(n)
使用自定义栈
class Solution {
public int trap(int[] height) {
return trap_A(height);
}
// 使用单调栈
public int trap_A(int []height){
int sz = height.length;
// 声明栈的大小
int stack[] = new int[sz];
// 声明栈顶指针
int point=-1;
int sumArea=0;
for(int i=0;i<sz;i++){
while(point !=-1 && height[stack[point]]<height[i]){
// 抛出左侧索引
int leftIdx = stack[point];
// 修改栈顶元素值
stack[point]=0;
--point;
if(point==-1){
break;
}
// 计算左侧边界
int leftedge = stack[point];
// 计算左右高度差
int minheight = Math.min(height[i],height[leftedge]);
// 计算面积
sumArea += (minheight-height[leftIdx])*(i-leftedge-1);
}
// 压入索引位置
stack[++point]= i;
}
return sumArea;
}
}自定义栈：栈顶指针为point=-1
每一次修改栈顶指针的值为：++point
栈顶指针指向的是当前栈顶的元素