解題思路
單調堆疊問題 具體可以看題解的影片演示
https://leetcode-cn.com/problems/trapping-rain-water/solution/yi-miao-jiu-neng-du-dong-de-dong-hua-jie-o9sv/
代碼
class Solution {
public int trap(int[] height) {
if (height.length<3){
return 0;
}
int ans = 0;
//記錄下標
LinkedList<Integer> stack = new LinkedList<>();
for (int i=0;i<height.length;i++){
if (stack.isEmpty()){
stack.add(i);
}else {
//保持單調遞減的堆疊
if (height[i]<=height[stack.getLast()]){
stack.add(i);
}else {
while (!stack.isEmpty() && height[i]>height[stack.getLast()]){
//當前堆疊頂的高度
int h = height[stack.getLast()];
stack.removeLast();
if (stack.isEmpty()){
break;
}
//取兩者高度差的較小值
int n = Math.min(height[i]-h,height[stack.getLast()]-h);
//兩點的下標距離
int index = i - stack.getLast()-1;
ans += n*index;
}
stack.add(i);
}
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347072.html
標籤：其他