leetcode 215

215. 数组中的第K个最大元素

这道题是找到数组中的第K个最大元素，里面有个陷阱就是惯性思维，一开始只简单的认为用数组嘛，这直接用桶排序不就完了，但自己真的太天真了。。。完全没想到数字还可以是负数啊，然后又干脆直接通过给数组的每个元素排序吧，那怎么输出呢？又不能按位置输出，因为可能其中包含重复的数字，那是要设置一个max值，然后每次得到数组中一个比max大的数就让另一个标记flag++吗 这也不行啊。
栈好像可以？每次得到一个栈中最大的数就让他出栈，等到出栈了k-1个大数之后，就对栈逆序，然后输出栈顶元素，但前提是栈中的元素需要排好大小，很麻烦啊，有没有更简单的做法呢，只需要创建，排序不用你管，那么只能是二叉树了，这就得用到堆。
思路就是创建一个小根堆，小根堆和小顶堆的概念又不一样，这是概念
然后再把原数组中的第K个元素之前的值给小根堆，让它自动排好序。
现在因为要求第K大的数字，那么需要比较的最少次数就是数组的size-k次。
那么就开始用数组的第k+1个元素开始和数组中的第一个元素比较大小，大的话，就直接让其入小根堆就好了.注意 这个小根堆始终由K个元素组成，当大于K个元素时，还要释放堆顶的元素。这个概念是保证首元素是第K个最大元素的关键。
依次循环后，堆就保留了前K个最大的元素，这样，堆顶的元素就是正确答案。
源代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        vector <int> minstack(k);
        for (int i = 0; i < k; i++) {
            minstack[i] = nums[i];
        }
        make_heap(minstack.begin(), minstack.end(), greater<int>());//创建小根堆
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > minstack[0]) {
                minstack.push_back(nums[i]);
                push_heap(minstack.begin(), minstack.end(), greater<int>());
            }
            if (minstack.size() > k) {
                pop_heap(minstack.begin(), minstack.end(), greater<int>());
                minstack.pop_back();
            }
        }
        return minstack[0];
    }
};