Java O(n) accepted solution


  • 1

    Steps:

    1. Find all valleys
    2. Merge these valleys based on their edge heights
    3. Calculate the amount of water each valley can contain
    class Solution {
        public int trap(int[] height) {
            if (height.length <= 1) {
                return 0;
            }
            
            int result = 0;
            
            List<int[]> endpoints = findEndpoints(height);
            List<int[]> mergedEndpoints = mergeEndpoints(endpoints, height);
            
            for (int[] eps : mergedEndpoints) {
                int start = eps[0];
                int end = eps[1];
                
                int edgeHeight = Math.min(height[start], height[end]);
                int currResult = edgeHeight * (end - start + 1);
                for (int j = start; j <= end; j++) {
                    currResult -= Math.min(height[j], edgeHeight);
                }
                
                result += currResult;
            }
            
            return result;
        }
        
        private List<int[]> findEndpoints(int[] height) {
            List<int[]> result = new ArrayList<>();
    
            boolean isInclining = height[1] > height[0];
            int trapStartIndex = height[1] < height[0] ? 0 : -1;
            
            for (int i = 1; i < height.length; i++) {
                if (height[i] == height[i - 1]) {
                    if (trapStartIndex != -1 && i == height.length - 1) {
                        result.add(new int[] { trapStartIndex, i });                 
                    }
                    
                    continue;
                }
                
                if (height[i] > height[i - 1]) {
                    isInclining = true;
                    
                    if (trapStartIndex == -1) {
                        continue;
                    }
                    
                    if (isInclining) {
                        if (i == height.length - 1) {
                            result.add(new int[] { trapStartIndex, i });
                            trapStartIndex = -1;
                        }
                    }
                } else {
                    if (trapStartIndex == -1) {
                        isInclining = false;
                        trapStartIndex = i - 1;
                        
                        if (i == height.length - 1) {
                            result.add(new int[] { trapStartIndex, i });
                        }                    
                    } else {
                        if (isInclining) {
                            isInclining = false;
                            result.add(new int[] { trapStartIndex, i - 1 });
                            trapStartIndex = i - 1;
                        }
                        
                        if (i == height.length - 1) {
                            result.add(new int[] { trapStartIndex, i });
                        }
                    }
                }
            }
            
            return result;
        }
        
        private List<int[]> mergeEndpoints(List<int[]> endpoints, int[] height) {
            List<int[]> result = new ArrayList<>();
            
            int i = 0;
            while (i < endpoints.size()) {
                int[] epsi = endpoints.get(i);
                
                if (height[epsi[0]] <= height[epsi[1]]) {
                    result.add(epsi);
                    i++;
                } else {
                    int[] curr = new int[] { epsi[0], epsi[1] };
                    
                    int j = i + 1;
                    int mergedIndex = i;
                    while (j < endpoints.size()) {
                        int[] epsj = endpoints.get(j);
                        
                        if (height[epsj[0]] >= height[epsi[0]]) {
                            mergedIndex = j - 1;
                            curr[1] = epsj[0];
                            break;
                        }
                        
                        if (height[epsj[1]] >= height[curr[1]]) {
                            curr[1] = epsj[1];
                            mergedIndex = j;
                            if (height[curr[1]] > height[curr[0]]) {
                                break;
                            }
                        }
                        
                        j++;
                    }
                    
                    result.add(curr);
                    
                    i = mergedIndex + 1;
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.