​​​​​​2099. 找到和最大的长度为 K 的子序列 - 力扣（LeetCode）

目录

 说明

思路

代码

---

 说明

和上一篇答案的主要不同是自己写了个pair提高了运行速度，代码核心部分并未改变。

首先放上运行结果：

思路

1. 利用pair，把元素值和其在原数组中的位置关联在一起.

2. 首先根据元素值val来构造最小堆，利用最小堆找出最大的k个元素；

3. 然后根据位置下标idx来调整最小堆；

4. 最后依次从堆顶取出元素值，放入最终的数组ans中.

代码

class Solution {
#define NOP 0
#define top 1
#define vacancy 0x7fffffff

    struct My_pair {
        int val;
        int idx;
        My_pair() :val(vacancy), idx(vacancy) {}
        My_pair(int v, int i) :val(v), idx(i) {}
        void form(int v, int i) {
            val = v;
            idx = i;
        }
    };
    My_pair make_My_pair(int v, int i) {
        return *new My_pair(v, i);
    }
    My_pair make_My_pair() {
        return *new My_pair();
    }

    enum subject { VAL, IDX };

    My_pair* minHeap;
    int k;

public:
    vector<int> maxSubsequence(vector<int>& nums, int K) {
        k = K;
        minHeap = new My_pair[k + 1];

        //build minHeap
        for (int idx = 0; idx != k; ++idx) {
            minHeap[idx + 1].form(nums[idx], idx);
        }
        for (int pos = k / 2; pos; --pos) {
            sink(minHeap[pos], pos, VAL);
        }
        //get k largest elements
        int size = nums.size();
        for (int idx = k; idx != size; ++idx) {
            My_pair intruder(nums[idx], idx);
            compare(intruder, minHeap[top], VAL) ?
                sink(intruder, top, VAL) : NOP;
        }

        //rectify minHeap with IDX
        for (int pos = k / 2; pos; --pos) {
            sink(minHeap[pos], pos, IDX);
        }
        //put elements into array successively
        vector<int> ans(k);
        for (int i = 0; i != k; ++i) {
            ans[i] = minHeap[top].val;
            sink(make_My_pair(), top, IDX);
        }

        return ans;
    }

    //core of priority queue
    int sink(My_pair pebble, int pos, subject X) {
        int bubble;
        while ((bubble = pos * 2) <= k) {
            bubble != k && compare(minHeap[bubble], minHeap[bubble + 1], X) ?
                ++bubble : NOP;
            if (compare(minHeap[bubble], pebble, X)) break;
            minHeap[pos] = minHeap[bubble];
            pos = bubble;
        }
        minHeap[pos] = pebble;
        return 0;
    }

    int compare(My_pair A, My_pair B, subject X) {
        return (!X && A.val > B.val) ||
            (X && A.idx > B.idx) ?
            1 : 0;
    }
};