Java, O(n) time and O(1) space without stack!


  • 1
    W

    public class Solution {
    /**
    * @param heights: an array of integers
    * @return: a integer
    */
    public int trapRainWater(int[] heights) {
    // write your code here
    if(heights == null || heights.length < 2){
    return 0;
    }

        int res = 0;
        
        int min = 0;
        int max = heights.length - 1;
        
        int minVal = heights[min];
        int maxVal = heights[max];
        
        while(max - min > 1){
            if(minVal <= maxVal){
                if(heights[min+1] > minVal){
                    minVal = heights[min+1];
                    min ++;
                }
                else{
                    res += minVal - heights[min+1];
                    min ++;
                }
            }
            else{
                if(heights[max-1] > maxVal){
                    maxVal = heights[max-1];
                    max --;
                }
                else{
                    res += maxVal - heights[max-1];
                    max --;
                }
            }
        }
        
        return res;
    }
    

    }


Log in to reply
 

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