|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法** 这个去重有意思|

|[0496.下一个更大元素I](https://github.com/youngyangyang04/leetcode/blob/master/problems/0496.下一个更大元素I.md)|栈|中等|**单调栈** 入门题目，但是两个数组还是有点绕的|

|[0501.二叉搜索树中的众数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0501.二叉搜索树中的众数.md)|二叉树|简单|**递归/中序遍历**|

|[0509.斐波那契数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0509.斐波那契数.md)|数组|简单|**递归****动态规划**|

|[0513.找树左下角的值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0513.找树左下角的值.md)|二叉树|中等|**递归****迭代**|

|[0515.在每个树行中找最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0515.在每个树行中找最大值.md)|二叉树|简单|**广度优先搜索/队列**|

|[0518.零钱兑换II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0518.零钱兑换II.md)|动态规划|中等|**动态规划** dp里求组合|

|[0763.划分字母区间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0763.划分字母区间.md)|贪心|中等|**双指针/贪心** 体现贪心尽可能多的思想|

|[0738.单调递增的数字](https://github.com/youngyangyang04/leetcode/blob/master/problems/0738.单调递增的数字.md)|贪心算法|中等|**贪心算法** 思路不错，贪心好题|

|[0739.每日温度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0739.每日温度.md)|栈|中等|**单调栈** 适合单调栈入门|

|[0746.使用最小花费爬楼梯](https://github.com/youngyangyang04/leetcode/blob/master/problems/0746.使用最小花费爬楼梯.md)|动态规划|简单|**动态规划** 入门题目和斐波那契额数列类似|

|[0767.重构字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0767.重构字符串.md)|字符串|中等|**字符串** + 排序+一点贪心|

|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md)|孤岛问题|中等|**bfs****dfs**|

|[0844.比较含退格的字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0844.比较含退格的字符串.md)|字符串|简单|**栈****双指针优化** 使用栈的思路但没有必要使用栈|

<palign='center'>

<imgsrc="https://img-blog.csdnimg.cn/20201215214102642.png"width=400 >

</p>

<palign="center">

<ahref="https://github.com/youngyangyang04/leetcode-master"><imgsrc="https://img.shields.io/badge/Github-leetcode--master-lightgrey"alt=""></a>

<ahref="https://img-blog.csdnimg.cn/20201115103410182.png"><imgsrc="https://img.shields.io/badge/刷题-微信群-green"alt=""></a>

<ahref="https://img-blog.csdnimg.cn/20201210231711160.png"><imgsrc="https://img.shields.io/badge/公众号-代码随想录-brightgreen"alt=""></a>

<ahref="https://space.bilibili.com/525438321"><imgsrc="https://img.shields.io/badge/B站-代码随想录-orange"alt=""></a>

<ahref="https://www.zhihu.com/people/sun-xiu-yang-64"><imgsrc="https://img.shields.io/badge/知乎-代码随想录-blue"alt=""></a>

<ahref="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><imgsrc="https://img.shields.io/badge/头条-代码随想录-red"alt=""></a>

</p>

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points[i] =[xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：points =[[10,16],[2,8],[1,6],[7,12]]

输出：2

解释：对于该样例，x = 6 可以射爆[2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

输入：points =[[1,2],[3,4],[5,6],[7,8]]

输出：4

示例 3：

输入：points =[[1,2],[2,3],[3,4],[4,5]]

输出：2

示例 4：

输入：points =[[1,2]]

输出：1

示例 5：

输入：points =[[2,3],[2,3]]

输出：1

提示：

* 0 <= points.length <= 10^4

* points[i].length == 2

* -2^31 <= xstart < xend <= 2^31 - 1

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？

尝试一下举反例，发现没有这种情况，**那么就试一试贪心吧！**

尝试一下举反例，发现没有这种情况。

但又想一下，如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，记录一下箭的数量就可以了。

如果真实的模拟射气球的过程，应该射一个，气球数组就remove一个元素，这样最直观，毕竟气球被射了。

以上为思考过程，已经确定下来使用贪心了，那么开始解题。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

**如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭**。

以题目示例：[[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

};

时间复杂度O(nlogn)

空间复杂度O(1)

* 时间复杂度O(nlogn)，因为有一个快排

* 空间复杂度O(1)

可以看出代码并不复杂。

注意题目中说的是：满足 xstart ≤ x ≤ xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆，

所以代码中`if (points[i][0] > points[i - 1][1])` 不能是>=

这道题目贪心的思路很简单也很直接，就是重复的一起射了，但本题我认为是有难度的。

就算思路都想好了，模拟射气球的过程，很多同学真的要去模拟了，实时把气球从数组中移走，这么写的话就复杂了。

而且寻找重复的气球，寻找重叠气球最小右边界，其实都有代码技巧。

贪心题目有时候就是这样，看起来很简单，思路很直接，但是一写代码就感觉贼复杂无从下手。

这里其实是需要代码功底的，那代码功底怎么练？

**多看多写多总结！**

**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**

**循序渐进学算法，认准[「代码随想录」](https://img-blog.csdnimg.cn/20200815195519696.png)，Carl手把手带你过关斩将！**

<palign='center'>

<imgsrc="https://img-blog.csdnimg.cn/20201216002707465.jpg"width=200 >

</p>

这个爬楼梯的问题和斐波那契数列问题很像。

读完题大家应该知道指定需要动态规划的，贪心是不可能了。

本题在动态规划里相对简单一些，以至于大家可能看个公式就会了，但为了讲清楚思考过程，我按照我总结的动规四步曲来详细讲解：

1. 确定dp数组以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

* 确定dp数组以及下标的含义

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义：第i个台阶所花费的最少体力为dp[i]。

**对于dp数组的定义，大家一定要清晰！**

* 确定递推公式

**可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]**。

那么究竟是选dp[i-1]还是dp[i-2]呢？

一定是选最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

**注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的**，因为题目中说了：第i个阶梯对应着一个非负数的体力花费值 cost[i]

* dp数组如何初始化

根据dp数组的定义，dp数组初始化其实是比较难的，因为不可能初始化为第i台阶所花费的最少体力。

那么看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。

所以初始化代码为：

* 确定遍历顺序

最后一步，递归公式有了，初始化有了，如何遍历呢？

本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶，而且dp[i]又dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来。

例如01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？ 以及在使用一维dp数组的时候遍历背包容量为什么要倒叙呢？ 这些都是遍历顺序息息相关。

公众号「代码随想录」后面在讲解动态规划的时候，还会详细说明这些细节，大家可以微信搜一波「代码随想录」，关注后就会发现相见恨晚！

分析完动规四步曲，整体C++代码如下：

classSolution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> dp(cost.size());

dp[0] = cost[0];

dp[1] = cost[1];

for (int i = 2; i < cost.size(); i++) {

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

}

return min(dp[cost.size() - 1], dp[cost.size() - 2]);

}

};

* 时间复杂度：O(n)

* 空间复杂度：O(n)

当然我不建议这么写，能写出版本一就可以了，直观简洁！