No.1 矩阵中的幸运数                                                             

解题思路

统计出每一行的最小值和每一列的最大值, 然后逐个比较就可以了.

时间复杂度: o(nm) 空间复杂度: o(n+m)

代码展示

class Solution {
   public List<Integer> luckyNumbers (int[][] matrix) {
       int n = matrix.length;
       int m = matrix[0].length;
       // rowMin[i] 表示第 i 行的最小值 (i 0-indexed)
       int[] rowMin = new int[n];
       Arrays.fill(rowMin, Integer.MAX_VALUE);
       // colMax[i] 表示第 i 列的最大值
       int[] colMax = new int[m];
       Arrays.fill(colMax, Integer.MIN_VALUE);
       // 遍历矩阵求出 rowMin 和 colMax
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               rowMin[i] = Math.min(rowMin[i], matrix[i][j]);
               colMax[j] = Math.max(colMax[j], matrix[i][j]);
           }
       }
       // 遍历矩阵求出答案
       List<Integer> res = new ArrayList<>();
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                   res.add(matrix[i][j]);
               }
           }
       }
       return res; 
   }
}

No.2 设计一个支持增量操作的栈

★解题思路

使用两个数组: 一个当作栈储存普通的值, 一个储存增量. 由于 increment() 操作是将栈底的 k 个元素都加上固定的值, 而栈的访问顺序只能是从栈顶, 所以我们没有必要将所有元素都加上这个值, 只需要将距离栈顶最近的位置标记上增量即可. 在我们弹栈时, 将增量下传.

代码展示

class CustomStack {

   private int[] stk, inc;
   private int size;

   public CustomStack(int maxSize) {
       stk = new int[maxSize];
       inc = new int[maxSize];
       size = 0;
   }

   public void push(int x) {
       if (size < stk.length) {
           stk[size] = x;
           inc[size] = 0;
           size++;
       }
   }

   public int pop() {
       if (size == 0) {
           return -1;
       }
       size--;
       int res = stk[size] + inc[size];  // 返回的结果就是原数值 + 增量
       if (size > 0) {  // 将增量下传
           inc[size - 1] += inc[size];
       }
       return res;
   }

   public void increment(int k, int val) {
       k = Math.min(k, size);
       // 只需要将距离栈顶最近的位置标记增量 + val 即可, 其它的会通过下传进行累加
       if (k > 0) {
           inc[k - 1] += val;  
       }
   }
}

No.3 将二叉搜索树变平衡

★解题思路

该题目要求新生成一棵树. 我们可以先取出原树的中序遍历序列 —— 由于是二叉搜索树, 所以中序序列一定是有序的.  然后问题就变成了由一个有序序列生成一棵平衡的二叉搜索树. 只需要递归地将中点作为根, 左侧的区间构造左子树, 右侧的区间构造右子树即可.

代码展示

class Solution {

   private List<Integer> values;

   public TreeNode balanceBST(TreeNode root) {
       values = new ArrayList<>();
       getInorder(root);
       return buildBST(0, values.size() - 1);
   }

   private void getInorder(TreeNode node) {
       if (node == null) {
           return;
       }
       getInorder(node.left);
       values.add(node.val);
       getInorder(node.right);
   }

   // 返回使用 values 的 [start, end] 区间的元素构造的平衡的 BST
   private TreeNode buildBST(int start, int end) {
       if (start > end) {
           return null;
       }
       int mid = (start + end) / 2;
       TreeNode node = new TreeNode(values.get(mid));
       node.left = buildBST(start, mid - 1);
       node.right = buildBST(mid + 1, end);
       return node;
   }
}

No.4 最大的团队表现值

★解题思路

假设团队中效率最低的人 P . 而 P 作为团队中效率最低的人时, 这个团队的最大表现值取决于其它成员的速度和.  贪心地 , 我们只需要在效率比  P 高的人中挑选出速度前  k - 1  大的人, 即可得到结果. 所以我们枚举效率最低的人 P , 计算得到他作为效率最低的人时团队的最大表现值. 在所有计算结果中取最优即可. 具体实现需要排序和堆, 见代码.

代码展示

class Solution {
   public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
       List<int[]> persons = new ArrayList<>(n);
       for (int i = 0; i < n; i++) {
           persons.add(new int[]{speed[i], efficiency[i]});  // p[0] 速度, p[1] 效率
       }
       persons.sort((p1, p2) -> p2[1] - p1[1]);  // 按照效率从大到小排序

       // 堆用于维护比当前枚举到的效率最小的人 P 的速度快的前 k - 1 个人
       Queue<Integer> heap = new PriorityQueue<>();
       long sum = 0;  // sum 表示 heap 中所有元素的和
       long res = 0;
       for (int[] p : persons) {
           // 计算以 p 为效率最低的人时, 团队的最大表现值
           sum += p[0];
           res = Math.max(sum * p[1], res);
           // 将 p 的速度加到堆中
           heap.add(p[0]);
           if (heap.size() == k) {
               sum -= heap.poll();
           }
       }
       return (int)(res % 1000000007);
   }
}