Just a c# solution.


  • 0
    N

    There is no builtin PriorityQueue in c#, for those problems that need to use PriorityQueue. There is less discussion.
    I just want to share my own implement about this question with a priority queue implemented by myself.
    btw, i didn't implement it in a heap way. just leverage the List.BinarySearch for less code.

    public class Solution {
        public int[,] directions = new int[,] { {1,0 }, {-1,0 }, {0,1 }, {0,-1 } };
        public int TrapRainWater(int[,] heightMap)
        {
            var total = 0;
            var m = heightMap.GetLength(0);
            var n = heightMap.GetLength(1);
            var visitied = new bool[m, n];
            var q = new BinaryHeap<int[]>((a, b) => a[2] - b[2]);
            for (var i = 0; i < m; ++i)
            {
                q.Enqueue(new int[] { i, 0, heightMap[i, 0] });
                q.Enqueue(new int[] { i, n-1, heightMap[i, n-1] });
                visitied[i, 0] = visitied[i, n - 1] = true;// don't forget to set visited when init the queue
            }
    
            for(var i=0;i< n; ++i)
            {
                q.Enqueue(new int[] { 0, i, heightMap[0, i] });
                q.Enqueue(new int[] { m-1, i, heightMap[m-1, i] });
                visitied[0, i] = visitied[m - 1, i] = true;
            }
    
            while (q.Count > 0)
            {
                var cell = q.Dequeue();
                for(var i = 0; i < 4; ++i)
                {
                    var x = cell[0] + directions[i, 0];
                    var y = cell[1] + directions[i, 1];
                    if (x < 0 || x == m || y < 0 || y == n || visitied[x, y]) continue;
                    total += Math.Max(0, cell[2] - heightMap[x, y]);
                    q.Enqueue(new int[] { x, y, Math.Max(cell[2], heightMap[x,y]) });
                    visitied[x, y] = true;
                }
            }
           
            return total;
        }
            
        public class BinaryHeap<T>
        {
            List<T> list = new List<T>();
            private Comparison<T> comparison;
            public BinaryHeap(Comparison<T> comparison)
            {
                this.comparison = comparison;
            }
    
            public int Count
            {
                get
                {
                    return list.Count;
                }
            }
    
            public T Dequeue()
            {
                var item = list[0];
                list.RemoveAt(0);
                return item;
            }
    
            public void Enqueue(T item)
            {
                if (list.Count == 0)
                {
                    list.Add(item);
                }
                else
                {
                    var i = list.BinarySearch(item, Comparer<T>.Create(comparison));
                    i = i >= 0 ? i : ~i;
                    if(list.Count == i)
                    {
                        list.Add(item);
                    }
                    else
                    {
                        list.Insert(i, item);
                    }
                }
            }
    
            public T Seek()
            {
                return list[0];
            }
        }
    }
    

Log in to reply
 

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