Java O(n^2) 11ms without Stack


  • 0
    G
    /*
    algorithm:
    1 from current index to left, l = K, if heights[l-1] <= height[l], keep moving left l--;
      if(real fall): heights[l-1] < heights[l] update fallpoint = l-1
      heights[fallpoint]++
      V--
    
    2 from current index to right, r = K, if heighs[r+1] <= height[r], keep moving right r++;
      if(real fall): heights[r+1] < heights[r] update fallpoint_r = r+1
      heights[fallpoint]++
      V--
    
    3 otherwise heights[K]++
      V--
    
    4 until V == 0
    */
    
    
    class Solution {
        public int[] pourWater(int[] heights, int V, int K) {
          if(heights == null || heights.length < 1) return new int[0];
          int n = heights.length;
          while(V > 0) {
            //left side check
            int l = K;
            int fall_l = l;
            while(l >= 1 && heights[l-1] <= heights[l]) {
              if(heights[l-1] < heights[l]) {
                fall_l = l-1;//up date fall point && get bottom line: heights[fall_l]
              }
              l--;
            }
    
            //right side check
            int r = K;
            int fall_r = r;
            while(r+1 < n && heights[r+1] <= heights[r]) {
              if(heights[r+1] < heights[r]) {
                fall_r = r+1;//up date fall point
              }
              r++;
            }
    
            //after moving left, there may be some cases:
            //case1: index l == k not move
            //case2: index l < k, but heights[l] == heights[k], not eventually fall left
            //case3: index l < k, heights[l] < heights[k], eventally fall left!
            if(l < K && heights[l] < heights[K]) {
              heights[fall_l]++;
            }
            //after moving left, there may be some cases:
            //case1: index r == k not move
            //case2: index r > k, but heights[r] == heights[k], not eventually fall right
            //case3: index r > k, heights[r] < heights[k], eventally fall left!
            else if(r > K && heights[r] < heights[K]) {
              heights[fall_r]++;
            }
    
            else if(fall_r == K && fall_r == K) {
              heights[K]++;
            }
    
            V--;
          }
    
          return heights;
        }
    }
    

Log in to reply
 

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