贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。
贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。
能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
盛最多水的容器leetcode题号：11
给定一个长度为 n 的整数数组
返回容器可以储存的最大水量（积最大）
[1, 8, 6, 2, 5, 4, 8, 3, 7]
初始时，左右指针分别指向数组的左右两端 ， 可以容纳的水量为 min(1,7)∗8=8。
此时我们需要移动一个指针。移动对应数字较小的那个指针
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
}
跳跃游戏II
leetcode题号：45
给你一个非负整数数组 nums ，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度，你的目标是使用最少的跳跃次数到达数组的最后一个位置。
如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}
最大数
leetcode题号：179
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
Arrays.sort()默认从小到大，若需从大到小需自定义（百度去吧）
输入：nums = [3,30,34,5,9]
输出：“9534330”
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
String numsToWord[] = new String[n];
for(int i=0;i
numsToWord[i] = String.valueOf(nums[i]);
}
//compareTo()方法比较的时候是按照ASCII码逐位比较的
//通过比较(a+b)和(b+a)的大小，就可以判断出a,b两个字符串谁应该在前面
//所以[3,30,34]排序后变为[34,3,30]
//[233，23333]排序后变为[23333，233]
Arrays.sort(numsToWord,(a,b)->{
return (b+a).compareTo(a+b);
});
//如果排序后的第一个元素是0，那后面的元素肯定小于或等于0，则可直接返回0
if(numsToWord[0].equals("0")){
return "0";
}
StringBuilder sb = new StringBuilder();
for(int i=0;i
sb.append(numsToWord[i]);
}
return sb.toString();
}
}
有效三角形的个数
leetcode题号：611
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
三指针:
我们固定 i，那么随着 j 的递增，不等式右侧 nums[i]+nums[j] 也是递增的
这样一来，我们就可以将 j 和 k 看成两个同向（递增）移动的指针
class Solution {
public int triangleNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < n; ++i) {
int k = i;
for (int j = i + 1; j < n; ++j) {
while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
++k;
}
ans += Math.max(k - j, 0);
}
}
return ans;
}
}
有效的括号字符串
leetcode题号：678
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )
- 任何右括号 ) 必须有相应的左括号 (
- 左括号 ( 必须在对应的右括号之前 )
- *可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
- 一个空字符串也被视为有效字符串。
当前字符为 ) : l 和 r 同时减一；
当前字符为 * ，右括号l-1，左括号r+1
当出现 l > r 说明上界为负数，即右括号过多，必然为非合法方案，返回 false。
class Solution {
public boolean checkValidString(String s) {
int l = 0, r = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
l++; r++;
} else if (c == ')') {
l--; r--;
} else {
l--; r++;
}
l = Math.max(l, 0);
if (l > r) return false;
}
return l == 0;
}
}
