leetcode 239 Sliding Window Maximum

这题是典型的堆排序算法，只是比一般的堆算法多了删除的操作，有两件事需要做：

１用一个hash表存储从输入数组索引到堆数组（用于实现堆的那个数组）所以的映射，以便在需要删除一个元素的时候能迅速定位到堆数组中的位置

２用一个set保存已经被删除的元素索引（这里指的是输入数组索引），这一点可选;还有一种做法就是直接将已删除元素的值设为最小INT_MIN，不过在leetcode里面并没有说清楚数据范围

class Solution {

public:

    unordered_map<int, int> dict;

    unordered_set<int> invalidSet;

    inline int LEFT(int i){

         return 2 * i + 1;

    }

    inline int RIGHT(int i){

        return 2 * i + 2;

    }

    inline int PARENT(int i){

        return (i - 1) / 2;

    }

    void max_heapify(int ind, vector<int>& arr, const vector<int>& value_arr){

        int l = LEFT(ind);

        int r = RIGHT(ind);

        int largest = ind;

        if(l < arr.size() && (invalidSet.find(arr[l]) == invalidSet.end())

            && (invalidSet.find(arr[largest]) != invalidSet.end()

                || value_arr[arr[l]] > value_arr[arr[largest]])){

            largest = l;

        }

        if(r < arr.size() && (invalidSet.find(arr[r]) == invalidSet.end())

            && (invalidSet.find(arr[largest]) != invalidSet.end()

                || value_arr[arr[r]] > value_arr[arr[largest]])){

            largest = r;

        }

        if (largest != ind){

            swap(dict[arr[ind]], dict[arr[largest]]);

            swap(arr[ind], arr[largest]);

            max_heapify(largest, arr, value_arr);

        }

    }

    void max_heap_insert(int ind, vector<int>& arr, const vector<int>& value_arr){

        arr.push_back(ind);

        dict[ind] = arr.size() - 1;

        int i = arr.size() - 1;

        while (i > 0 && (invalidSet.find(arr[PARENT(i)]) != invalidSet.end()

                    || value_arr[arr[PARENT(i)]] < value_arr[arr[i]])){

            swap(dict[arr[i]], dict[arr[PARENT(i)]]);

            swap(arr[i], arr[PARENT(i)]);

            i = PARENT(i);

        }

    }

    void max_heap_delete(int ind, vector<int>& arr, const vector<int>& value_arr){

        invalidSet.insert(ind);

        max_heapify(dict[ind], arr, value_arr);

    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> result;

        if(nums.size() == 0)

            return result;

        vector<int> h;

        h.reserve(nums.size());

        for(int i = 0; i < k; i++)

            max_heap_insert(i, h, nums);

        result.push_back(nums[h[0]]);

        for(int i = k; i < nums.size(); i++){

            max_heap_delete(i - k, h, nums);

            max_heap_insert(i, h, nums);

            result.push_back(nums[h[0]]);

        }

        return result;

    }

};

巴特西

leetcode 239 Sliding Window Maximum

最新文章

热门文章