public class DayCode {    public static void main(String[] args) {        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};        int ans = new DayCode().trap(height);        int ans1 = new DayCode().trap1(height);        System.out.println("ans is " + ans);        System.out.println("ans1 is " + ans1);    }
    /**     * 时间复杂度 O (n * n)     * 空间复杂度 O (1)     * 题目链接: https://leetcode-cn.com/problems/volume-of-histogram-lcci/     *     * @param height     * @return     */    public int trap(int[] height) {        int result = 0;        int heightLength = height.length;        for (int i = 1; i < heightLength - 1; i++) {            int maxLeft = 0, maxRight = 0;            for (int left = i; left >= 0; left--) {                maxLeft = Math.max(maxLeft, height[left]);            }            for (int right = i; right < heightLength; right++) {                maxRight = Math.max(maxRight, height[right]);            }            result += Math.min(maxLeft, maxRight) - height[i];        }
        return result;    }

    /**     * 时间复杂度 O(n)     * 空间复杂度 O(n)     * 题目链接: https://leetcode-cn.com/problems/volume-of-histogram-lcci/     *     * @param height     * @return     */    public int trap1(int[] height) {        int ans = 0;        Deque<Integer> stack = new ArrayDeque<>();        int n = height.length;        for (int i = 0; i < n; i++) {            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {                int top = stack.pop();                if (stack.isEmpty()) {                    break;                }                int left = stack.peek();                int currentWidth = i - left - 1;                int currentHeight = Math.min(height[left], height[i]) - height[top];                ans += currentWidth * currentHeight;            }            stack.push(i);        }
        return ans;    }}