image.png

package l42;
class Solution {
    public int trap(int[] a) {
        int p=0, q=a.length-1;
        int res=0;
        // 需要額外維護左右2邊到目前為止的max
        int maxLeft=0, maxRight=0;
        while(p<q) {
            if(a[p]>a[q]) {
                res+=Math.max(0, maxRight-a[q]);
                maxRight=Math.max(maxRight, a[q]);
                q--;
            } else {
                res+=Math.max(0, maxLeft-a[p]);
                maxLeft=Math.max(maxLeft, a[p]);
                p++;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
}