給定一個直方圖(也稱柱狀圖)，假設有人從上面源源不斷地倒水，最后直方圖能存多少水量?直方圖的寬度為 1。

上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方圖，在這種情況下，可以接 6 個單位的水（藍色部分表示水）。 感謝 Marcos 貢獻此圖。

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6

解題思路

維護一個單調遞減的棧，當遍歷到的元素大于棧中元素時，就將棧中的兩個元素和當前元素組成一個接雨水的區域

代碼

class Solution {public int trap(int[] height) {Stack<Integer> stack=new Stack<>();int n=height.length,res=0;for(int i=0;i<n;i++){while (!stack.isEmpty()&&height[i]>height[stack.peek()]){int top=stack.pop();if(stack.isEmpty())break;int l=stack.peek();int weight=i-l-1;int h=Math.min(height[l],height[i])-height[top];res+=h*weight;}stack.push(i);}return res;} }

總結

以上是生活随笔為你收集整理的leetcode 面试题 17.21. 直方图的水量（单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。