2099. 找到和最大的长度为 K 的子序列 - 力扣(LeetCode) (leetcode-cn.com)
首先放上运行结果:
思路
利用pair,把元素值和其在原数组中的位置关联在一起.
首先根据元素值val来构造最小堆,利用最小堆找出最大的k个元素;
然后根据位置下标idx来调整最小堆;
最后依次从堆顶取出元素值,放入最终的数组ans中.
代码
#define NOP 0
#define top 1
#define vacancy 0x7fffffff
class Solution {
typedef pair<int, int> cor;
enum subject { VAL, IDX };
cor* minHeap;
int k;
public:
vector<int> maxSubsequence(vector<int>& nums, int K) {
k = K;
minHeap = new cor[k + 1];
//build minHeap
for (int idx = 0; idx != k; ++idx) {
minHeap[idx + 1] = make_pair(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) {
cor intruder = make_pair(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].first;
sink(make_pair(vacancy, vacancy), top, IDX);
}
return ans;
}
//core of priority queue
int sink(cor 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(cor A, cor B, subject X) {
return (!X && A.first > B.first) ||
(X && A.second > B.second) ?
1 : 0;
}
};