力扣第217场周赛

桃扇骨 2022-12-25 05:54 115阅读 0赞

#### 1、最富有客户的资产总量 ####

##### [题目传送门][Link 1] #####

##### 题目描述 #####

> 给你一个 m x n 的整数网格 accounts ，其中 accounts\[i\]\[j\] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
> 
> 客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

###### 示例 1 ######

> 输入：accounts = \[\[1,2,3\],\[3,2,1\]\]  
> 输出：6  
> 解释：  
> 第 1 位客户的资产总量 = 1 + 2 + 3 = 6  
> 第 2 位客户的资产总量 = 3 + 2 + 1 = 6  
> 两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。

###### 示例 2 ######

> 输入：accounts = \[\[1,5\],\[7,3\],\[3,5\]\]  
> 输出：10  
> 解释：  
> 第 1 位客户的资产总量 = 6  
> 第 2 位客户的资产总量 = 10  
> 第 3 位客户的资产总量 = 8  
> 第 2 位客户是最富有的，资产总量是 10

###### 示例 3 ######

> 输入：accounts = \[\[2,8,7\],\[7,1,3\],\[1,9,5\]\]  
> 输出：17

##### 提示 #####

*  m == accounts.length
 *  n == accounts\[i\].length
 *  1 <= m, n <= 50
 *  1 <= accounts\[i\]\[j\] <= 100

##### 思路 #####

水题，只需要把每个人的资产加起来求出总资产然后求出总资产最大值即可

##### 代码 #####

class Solution { 
        public int maximumWealth(int[][] accounts) { 
            int len = accounts.length;
            int max = 0;
            for (int i = 0; i < len; i++) { 
                int l = accounts[i].length;
                int sum = 0;
                for (int j = 0; j < l; j++) { 
                    sum += accounts[i][j];
                }
                max = Math.max(max, sum);
            }
            return max;
        }
    }

#### 2、找出最具竞争力的子序列 ####

##### [题目传送门][Link 2] #####

##### 题目描述 #####

> 给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
> 
> 数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
> 
> 在子序列  a 和子序列  b 第一个不相同的位置上，如果  a  中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，\[1,3,4\] 比 \[1,3,5\] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

###### 示例 1 ######

> 输入：nums = \[3,5,2,6\], k = 2  
> 输出：\[2,6\]  
> 解释：在所有可能的子序列集合 \{\[3,5\], \[3,2\], \[3,6\], \[5,2\], \[5,6\], \[2,6\]\} 中，\[2,6\] 最具竞争力。

###### 示例 2 ######

> 输入：nums = \[2,4,3,3,5,4,9,6\], k = 4  
> 输出：\[2,3,3,4\]

##### 提示 #####

*  1 <= nums.length <= 105
 *  0 <= nums\[i\] <= 109
 *  1 <= k <= nums.length

##### 思路 #####

首先，暴力搜索肯定不行，会超时  
这道题需要使用单调队列  
思路不太好讲（我讲不太清楚），还是调试着慢慢理解吧

大致流程：  
创建一个长度为 k 的结果数组，使它的内部的元素是单调递增的，每遇到一个元素，将数组中比这个元素大的元素全部去掉，然后再将该元素放入数组中，如果数组满了就不再往里面放了，在去掉数组中比当前元素大的所有元素时需要判断，此元素后面的元素个数够不够放满结果数组的，如果不够，则不再去掉数组中比该元素大的元素

##### 代码 #####

class Solution { 
        public int[] mostCompetitive(int[] nums, int k) { 
            int[] res = new int[k];
            int p = 1;
            res[0] = nums[0];
            for (int i = 1; i < nums.length; i++) { 
                while (p > 0 && nums[i] < res[p - 1] && nums.length - i + p > k) { 
                    p--;
                }
                if (p != k) { 
                    res[p++] = nums[i];
                }
            }
            return res;
        }
    }

###### 后面三四题不会~ ######

##### 以上 #####

ヾ(≧∪≦\*)ノ〃

[Link 1]: https://leetcode-cn.com/problems/richest-customer-wealth/
[Link 2]: https://leetcode-cn.com/problems/find-the-most-competitive-subsequence/