406
题目：
假设有打乱顺序的一群人站成一个队列，数组
people表示队列中一些人的属性（不一定按顺序）。每个people[i] = [hi, ki]表示第i个人的身高为hi，前面 正好 有ki个身高大于或等于hi的人。 请你重新构造并返回输入数组people所表示的队列。返回的队列应该格式化为数组queue，其中queue[j] = [hj, kj]是队列中第j个人的属性（queue[0]是排在队列前面的人）。 示例 1： >输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] >解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。 示例 2： >输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]] 提示：
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.length- 题目数据确保队列可以被重建
思路：
大致意思就是 people.length个人， 每个人的身高为people[i][0]（i 为第i个人） ，与此同时在他前面有people[i][1]个人身高更高或者相同的人。 但是这些人是被打乱顺序的 ，这里需要我们按照每个人的升高和 在他前面的人个数 ， 给他们重新排序。使得排序后的people符合测试用例的result。
仅仅是这样， 我的理解，我这边也看网上有个各种比喻。 比喻来比喻去也就那样， 测试用例中还有hi == 0 的，这个升高为 0的人你怎么比喻？ 所以理解题意即可。
首先，需要给这些人进行排序， 因为题目中要求 编号为i的人 ，身高更高或者相同的人有people[i][1]个。 所以先按照身高进行排序 ， 如果身高相同， 那么就按照后面的身高相同或更高的人的个数进行排序。
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {
return person2[0] - person1[0];
} else {
return person1[1] - person2[1];
}
}
});得到的结果就是按照身高列成有序的二位数组， 这个顺序就是按照身高和 个数结合的，但是还不完整， 这个结合只是争对身高相同的人。对于身高不同的需要继续处理。
以题目中的案例一为例：
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
排序之后的队列应该是：
[[7,0],[7,1] ,[6,1] ,[5,0], [5,2] , [4,4] ]
当然这只是初步处理，还需要达到：返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第j个人的属性（queue[0] 是排在队列前面的人）。 这个要求 。
所以就需要对排序好的队列 做入队出队 处理 ，这要得到的结果才是题目要求的 result
实现
代码语言：javascript复制class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {
return person2[0] - person1[0];
} else {
return person1[1] - person2[1];
}
}
});
List<int[]> ans = new ArrayList<int[]>();
for (int[] person : people) {
ans.add(person[1], person);
}
return ans.toArray(new int[ans.size()][]);
}
}860
题目
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。 示例 1：
- 输入：[5,5,5,10,20]
- 输出：true
- 解释：
- 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
- 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
- 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
- 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
- 输入：[5,5,10]
- 输出：true
示例 3：
- 输入：[10,10]
- 输出：false
示例 4：
- 输入：[5,5,10,10,20]
- 输出：false
- 解释：
- 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
- 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
- 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
- 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
- 0 <= bills.length <= 10000
- bills[i] 不是 5 就是 10 或是 20
思路
就是按照题目中的给的用例给用户找零钱， 但是刚开始 你手中是没钱的 ，只有水。当用户给你钱你找不起的时候， 就是返回false的时候 。而且你只有三种钱5,10,20 所以，即使你有钱，但是没有零钱， 也得返回false。
按照这个思路， 直接一路写下来就好。没什么好的思路….
实现
代码语言：javascript复制class Solution {
public boolean lemonadeChange(int[] bills) {
int ten = 0; // 10 元的数量
int five = 0 ; // 5元的数量
int twenty = 0; //20 的数量
for(int i= 0 ; i< bills.length ; i ){
if(bills[i] == 5){
five ;
}
if(bills[i] == 10){
//需要先减少一个5 元， 然后再加一个10 元的数量
if(five <= 0){
return false;
}
ten ;
five--;
}
if(bills[i] == 20){
//先判断10 元的数量够不够 或者 5 元的数量够不够 ，如果不够就false
if(five > 0 && ten > 0){
five--;
ten--;
twenty ;
}
//需要减少一个5 元的数量 && 一个 10 元的数量
else if(five >= 3 ){
//直接减少3 个5 元的数量
five -= 3;
twenty ;
}else{
return false;
}
}
}
return true;
}
}53
题目：
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 输入：nums = [1] 输出：1 示例 3： 输入：nums = [5,4,-1,7,8] 输出：23 提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路
这道题的解法有很多中， 可以使用贪心， 也可以使用暴力 还可以使用动态规划。
这里主要以贪心算法为主学习。
题目要求：具有最大和的连续子数组（子数组最少包含一个元素） 。我们这里使用滑动窗口的方式 累加，如果遇到累加的结果 小于 0， 那么直接跳到下一个位置 重新开始累加。
同理， 如果这里遇到刚开始就有负数的情况，需要直接跳到有正数的位置开始， 因为和有负数， 那就不可能达到最大和的要求。
通过sum = Math.max(sum, count); 来实现不断的更新最大的累加和。
实现
代码语言：javascript复制class Solution {
public int maxSubArray(int[] nums) {
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i ){
count = nums[i];
sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
if (count <= 0){
count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
}
return sum;
}
}
