贪心算法
贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。
使用条件
- 贪心选择性质 一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 [4] 。
- 最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。
11. 盛最多水的容器
题目详情
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
题目解释
暴力解法，O(n^2)，每个i,j组合都计算一下。
双指针移动短板 若向内 移动短板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。 若向内 移动长板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小。 移动短板消去的状态不会影响结果.
public int maxArea(int[] height) {
int max = Integer.MIN_VALUE;
int l = 0;
int r = height.length - 1;
while (l < r) {
int cur = Math.min(height[l], height[r]) * (r - l);
max = Math.max(max, cur);
//移动小端
if (height[l] <= height[r]) {
l++;
} else {
r--;
}
}
return max;
}
406.根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
输入：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]] 是重新构造后的队列。
排序后插入，做该题时又在想O(n)的方法了，结果题解也是O(n^2)
public int[][] reconstructQueue(int[][] people) {
//排序按身高倒序，前面人数顺序排序
Arrays.sort(people, (o1, o2) -> {
if(o1[0] == o2[0]){
return Integer.compare(o1[1], o2[1]);
} else {
return Integer.compare(o2[0], o1[0]);
}
});
//每次都把人往前面插入
List<int[]> ans = new ArrayList<>();
for (int[] person : people) {
ans.add(person[1], person);
}
return ans.toArray(new int[ans.size()][]);
}
581. 最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
输入：nums = [2,6,4,8,10,9,15] 输出：5 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
解答
排序后比对不就完了？？ O(nlogn)的简单思路算法
public int findUnsortedSubarray(int[] nums) {
int[] sorted = Arrays.copyOf(nums, nums.length);
Arrays.sort(sorted);
int st = -1;
int ed = -1;
for (int i = 0; i < nums.length; i++) {
if(nums[i] != sorted[i]){
if(st == -1){
st = i;
} else {
ed = i;
}
}
}
if(st == -1){
return 0;
} else {
return ed - st + 1;
}
}
- 找到小于最大值的最右边界
- 找到大于最小值的最左边界
- 由这两个值可以确定无序连续子数组
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int maxn = Integer.MIN_VALUE, right = -1;
int minn = Integer.MAX_VALUE, left = -1;
for (int i = 0; i < n; i++) {
//遍历整个数组寻找无序右边界，找到小于最大值的最右边界
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
//遍历整个数组寻找无序左边界，找到大于最小值的最左边界
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right == -1 ? 0 : right - left + 1;
}
621.任务调度器
题目详情
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2 输出：8 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B 在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
题目解答
基本思路，每次执行选择当前最多的任务，且不在冷静期的任务执行
代码略
编排的思路
- 假设A,B为最多的任务数量为max，相同数目的任务数为num，那么执行的基础结构即 A B x x A B x x …A B x A B
- 剩余的任务要么就是全部插入了那么长度就是 (max + 1) * (n-1) + num;
- 剩余的任务没有排满，那么插空完之后就是加在末尾，此时没有空闲实际执行次数为tasks.length。
public int leastInterval(char[] tasks, int n) {
if (n == 0) {
return tasks.length;
}
int[] nameLessTasks = new int[26];
for (char c : tasks) {
nameLessTasks[c - 'A']++;
}
Arrays.sort(nameLessTasks);
int max = nameLessTasks[25];
int maxSameCount = 0;
// 基础结构即 a x x a x x ...a x x a
for (int i = 25; i >= 0; i--) {
if (nameLessTasks[i] == max) {
maxSameCount++;
} else {
break;
}
}
return Math.max(tasks.length, (n + 1) * (max - 1) + maxSameCount);
}
