Day13. Sliding window maximum value, top K high frequency elements

Day13. Sliding window maximum value, top K high frequency elements

0239. Sliding window maximum

Link: 0239. Sliding window maximum

Monotonic queue: The queue is monotonic. In order to maintain this monotonicity, when adding elements to the tail of the queue, if the previous element and the current element do not satisfy the monotonic relationship, remove the previous element until the previous element satisfies monotonicity or the queue is empty. Stop when , and then add the element.

Taking the monotonically decreasing queue as an example, the preceding element must be greater than or equal to the following element, and the head element is the largest element.
When adding an element to the tail, if the current value is greater than the tail element, and the condition that the preceding element is greater than the following element is not satisfied, the tail element is removed, and the element is added until the queue is empty or the preceding element is greater than the current element.

Similarly, when removing elements, in order to prevent elements still in the window from being removed from the queue, only when the element to be removed is equal to the element at the head of the queue, it is removed.
The head is always the largest number. If the value to be pop is not equal to the head value, it will either be behind the head value, or it will be squeezed out when the current head value is push ed.

// Monotonically decreasing queue
class MonoDecQueue {
public:
    void push(int val)
    {
        // If there is a value smaller than the current value in front of the value to be added, that is, at the end of the queue, remove it.
        // Ensure that the queue at the front is large and monotonically decreasing
        while (!_dq.empty() && val > _dq.back()) {
            _dq.pop_back();
        }
        _dq.push_back(val);
    }
    void pop(int val)
    {
        // pop only when the header value is equal to the value to be popped
        // The head is always the largest number, if the value to be pop is not equal to the head value
        // Either behind the header value or squeezed out on push
        if (!_dq.empty() && _dq.front() == val) {
            _dq.pop_front();
        }
    }
    int front()
    {
        return _dq.front();
    }

private:
    deque<int> _dq;
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> res;
        if (nums.size() < k) {
            return res;
        }
        MonoDecQueue mdq;
        for (size_t i = 0; i < k; ++i) {
            mdq.push(nums[i]);
        }
        int curMax = mdq.front();
        res.push_back(curMax);
        for (size_t i = 1; i <= nums.size() - k; ++i) {
            // The previous element is removed from the window
            mdq.pop(nums[i - 1]);
            // new elements enter the window
            mdq.push(nums[i + k - 1]);
            curMax = mdq.front();
            res.push_back(curMax);
        }
        return res;
    }
};

0347. Top K high frequency elements

Link: 0347. Top K high frequency elements

Idea: With the help of the priority queue, the small value priority queue, that is, the small element is in the front. What is needed is the element with the largest k first. When the queue size is greater than k, the head of the queue is the smallest element and can be removed directly. If a large-value priority queue is used, it is inconvenient to remove.

Small value priority queue, the comparison object is lhs>rhs. If you want the smaller elements to be in the front, you must make the front elements larger than the back elements in the judgment.

// Build a small top heap, small at the head of the queue
// Because the first k is the largest, when the queue size reaches k, the head of the queue is the smallest, and it is removed directly
// If you use a large top heap, it is not easy to remove
struct Cmp {
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs)
    {
        return lhs.second > rhs.second;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k)
    {
        unordered_map<int, int> cntMap;
        for (int i : nums) {
            cntMap[i]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> minQue;
        for (auto& p : cntMap) {
            minQue.push(p);
            if (minQue.size() > k) {
                minQue.pop();
            }
        }
        vector<int> res(minQue.size());
        size_t ind = res.size() - 1;
        while (!minQue.empty()) {
            auto& t = minQue.top();
            res[ind] = t.first;
            --ind;
            minQue.pop();
        }
        return res;
    }
};

Tags: C++ Algorithm data structure leetcode Hash table

Posted by papacostas on Thu, 10 Nov 2022 19:11:56 +0300