每日一刷leetcode（第k大的值及杨辉三角）

703. 数据流中的第 K 大元素

难度简单227 收藏 分享 切换为英文 接收动态 反馈

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

官方解法（使用优先级队列）:

class KthLargest {
    private PriorityQueue<Integer> queue;
    private int k;
    public KthLargest(int k, int[] nums) {
        queue=new PriorityQueue<>();
        this.k=k;
        for(int num:nums){
            add(num);
        }
    }
    
    public int add(int val) {
        if(queue.size()<k){
            queue.offer(val);
        }else if(queue.peek()<val){
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

119. 杨辉三角 II

难度简单223 收藏 分享 切换为英文 接收动态 反馈

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 *k *行。

image

在杨辉三角中，每个数是它左上方和右上方的数的和.

示例:

输入: 3
输出: [1,3,3,1]

解法1（递归求解）:

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //递归解法
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<=rowIndex;i++){
            List<Integer> row=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(j==0||j==i){
                    row.add(1);
                }else{
                    row.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
                }
            }
            list.add(row);
        }
        return list.get(rowIndex);
    }
}

优化：由于每一次都只用到了上一层的数据，所以只要保存上一层的数据就够了。这样在空间复杂度上可以提升一点。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //递归解法
        List<Integer> pre=new ArrayList<>();
        for(int i=0;i<=rowIndex;i++){
            List<Integer> cur=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(j==0||j==i){
                    cur.add(1);
                }else{
                    cur.add(pre.get(j-1)+pre.get(j));
                }
            }
            pre=cur;
        }
        return pre;
    }
}

再优化以下：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //递归解法
        List<Integer> row=new ArrayList<>();
        row.add(1);
        for(int i=1;i<=rowIndex;i++){
            row.add(0);
            for(int j=i;j>0;j--){
                row.set(j,row.get(j)+row.get(j-1));
            }
        }
        return row;
    }
}