腾讯光子

21. 第 k 大的数

难度感：medium

题目

给定无序数组和整数 k，返回数组中第 k 大的元素。

题解

• 可以用小顶堆维护当前最大的 k 个数，堆顶就是第 k 大。
• 遍历元素入堆，堆大小超过 k 就弹出最小值。
• 这个方法稳定好写，适合技术环节现场手撕。

复杂度：O(n log k) 时间，O(k) 空间。

C# 答案

using System.Collections.Generic;

public class Solution
{
    public int FindKthLargest(int[] nums, int k)
    {
        SortedDictionary<int, int> heap = new SortedDictionary<int, int>();
        int size = 0;

        foreach (int x in nums)
        {
            heap[x] = heap.ContainsKey(x) ? heap[x] + 1 : 1;
            size++;
            if (size > k)
            {
                int min = FirstKey(heap);
                if (--heap[min] == 0) heap.Remove(min);
                size--;
            }
        }

        return FirstKey(heap);
    }

    private int FirstKey(SortedDictionary<int, int> map)
    {
        foreach (var kv in map) return kv.Key;
        return -1;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
        for (int x : nums) {
            pq.push(x);
            if ((int)pq.size() > k) pq.pop();
        }
        return pq.top();
    }
};

---

22. 最长上升子序列

难度感：medium

题目

给定整数数组，返回最长严格递增子序列的长度。

题解

• tails[i] 表示长度为 i+1 的递增子序列的最小可能结尾。
• 每个数用二分找到第一个 >= x 的位置替换。
• tails 不一定是最终序列，但长度就是答案。

复杂度：O(n log n) 时间，O(n) 空间。

C# 答案

using System;

public class Solution
{
    public int LengthOfLIS(int[] nums)
    {
        int[] tails = new int[nums.Length];
        int size = 0;

        foreach (int x in nums)
        {
            int l = 0, r = size;
            while (l < r)
            {
                int mid = l + (r - l) / 2;
                if (tails[mid] < x) l = mid + 1;
                else r = mid;
            }

            tails[l] = x;
            if (l == size) size++;
        }

        return size;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        return (int)tails.size();
    }
};