思路一：参考 ，用 stack 做辅助

public class Solution {    public int trap(int[] heights) {        int result = 0;        Stack
     
       stack = new Stack<>();        for (int i = 0; i < heights.length; i++) {            while (!stack.isEmpty() && heights[stack.peek()] < heights[i]) {                int tmp = stack.pop(); // index of bottom                int height = stack.isEmpty() ? 0 : Math.min(heights[stack.peek()], heights[i]) - heights[tmp];                int width = stack.isEmpty() ? 0 : i - stack.peek() - 1;                result += height * width;             }            stack.push(i);        }        return result;    }}
     

 

思路二：dynamic programming