---

C++基础知识学习：

1、 “a”和‘a’的区别：
str = “a”输出的就是a这个字母；
str = ‘a’，'a’是ASCII码，输入或输出时自动将ASCII码，输出为65。
【注】：1、限制条件是只能对有ASCII码的字符使用单引号，如’ab’就不可以。2、+ - * /等，用“”，即：“+”、“-”、“*”、“/”等。

2、 string和char之间的关系：
例题：
string a = “12345”;
char num = a[0]; // 对应的是‘1’

3、 string型转char型，（用：.c_str()）
代码：
char c[20];
string s = “1234”;
strcpy(c, s.c_str());
参考文章：C++中的c_str()函数用法
4、 string型转int的一种方法：
string s = “2w14852e”；
int a = s[5]；
cout << a << endl；// 得a为5

5、 C++中stoi和atoi函数：
头文件：#include < string >
例题：
char s1[5] = “3456”;
std::string s2 = “12345”;
int v1 = atoi(s1); // 将char转换为int型
int v2 = stoi(s2); // 将string转换为int型，一般都用这个***********************************************
std::cout << v1 << std::endl; // 输出3456
std::cout << v2 << std::endl; // 输出12345

6、 vector的注意点
1> 用push_back添加元素，初始化的时候不必指出大小，例：vector< int > vec; vec.push_back(10);
2> 当vector当数组应用，初始化的时候需要指出大小，例：vector< int > vec(1); vec[0] = 10;
3> 定义：vector<vector< int >> result;************************************
result.push_back({0, 1}); result.push_back({2, 3});
result = [[0, 1], [2, 3]];

7、 一般会用到的最小值、最大值
INT_MIN = -2^31
INT_MAX = 2^31 - 1

8、 初始化longlong最小值：
long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
【注】：LONG_MAX

9、 注意(2<<0) 相当于2^1或者pow(2, 1); //a的b次方

10、 vector< int > 型转string型（或者：int型转string，例2）
例1：
vector< int > path;
string sPath;
sPath += to_string(path[i])
例2：
int n;
string num = to_string(n);

11、 C++中substr()函数用法详解

12、 定义n * n的二维数组（内元素为’.'）
std::vector< std::string > chessboard(n, std::string(n, ‘.’));

13、 insert函数
参考文章：C++中的insert()函数
14、
vector< string >& w;
unordered_set< string > t(w.begin(), w.end());
15、
当int不够表示，并且都是正数的话用uint试试，最大可写uint64_t
参考大佬：
1、C++中将string类型转化为int 类型

一、数组

例题

1、704 二分查找

【相关题目推荐】：
35.搜索插入位置
34.在排序数组中查找元素的第一个和最后一个位置
69.x 的平方根
367.有效的完全平方数

2、27 移除元素

【相关题目推荐】：
26.删除排序数组中的重复项
283.移动零
844.比较含退格的字符串
977.有序数组的平方

3、977 有序数组的平方
4、209 长度最小的子数组

【相关题目推荐】：
904.水果成篮
76.最小覆盖子串

5、59 螺旋矩阵 II

【相关题目推荐】：
54.螺旋矩阵
剑指Offer 29.顺时针打印矩阵

二、链表

参考理论

参考理论：关于链表，你该了解这些！

C/C++的定义链表节点方式

// 单链表
struct LinkedNode {int val;	// 节点上存储的元素LinkedNode *next;	// 指向下一个节点的指针LinkedNode ( int x ): val ( x ), next ( nullptr ) {}	// 节点的构造函数
};// 实例
class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点size = 0;}
private:int size;LinkedNode* dummyHead;
};

知识点

// 1、移动节点依次读取链表的各个节点（打印链表）
LinkedNode* dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
LinkedNode* cur = dummyHead;while (cur -> next != nullptr) {cout << cur -> next -> val << " ";cur = cur -> next;	// 指向链表的节点移动}
cout << endl;// 2、删除链表的一个节点
LinkedNode* dummyHead = new LinkedNode(0);
LinkedNode* cur = dummyHead;
while("根据题目条件写") {cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
size--;	// 链表长度减1
// 3、指向
// cur指向pre
pre == cur -> next;

例题

1、203 移除链表元素
2、206 反转链表
3、24 两两交换链表中的节点
4、19 删除链表的倒数第 N 个结点
5、面试题 02.07 链表相交
6、142 环形链表 II

三、哈希表

参考理论

参考理论：哈希表

例题

1、242 有效的字母异位词

【相关题目推荐】：
383.赎金信
49.字母异位词分组
438.找到字符串中所有字母异位词

2、349 两个数组的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set; // 存放结果// 此处将nums1中的元素拷贝进nums_set，并且由于nums_set是unordered_set<int>数据格式，有效启到了去重的作用，即：// 当nums1: {1, 2, 2}，那么nums_set: {1, 2}unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) != nums_set.end()) {// 此处result_set插入num值也有去重的效果，即：// 当连续插入两个相同的元素例如：2，2；但result_set中只会存一个2result_set.insert(num);}}// 将result_set里面的数值拷贝以vector<int>的数据格式输出return vector<int>(result_set.begin(), result_set.end());}
};

3、202 快乐数
4、1 两数之和
5、454 四数相加 II
6、383 赎金信
7、15 三数之和（这题推荐使用双指针）
8、18 四数之和

四、字符串

例题

1、344 反转字符串
2、541 反转字符串 II
3、剑指 Offer 05 替换空格
【注】：其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
4、151 翻转字符串里的单词
5、剑指 Offer 58 - II 左旋转字符串
6、28 实现 strStr()

KMP算法

KMP算法：原理详解
前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力

// 创建next数组int next[s.size()];//构建模式串的next表void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) {j = next[j - 1];}if (s[i] == s[j]) {j++;}next[i] = j;}}

7、459 重复的子字符串

五、双指针法

例题

1、27 移除元素
2、344 反转字符串
3、剑指 Offer 05 替换空格
4、151 颠倒字符串中的单词
5、206 反转链表
6、19 删除链表的倒数第 N 个结点
7、面试题 02.07 链表相交
8、142 环形链表 II
9、15 三数之和（这题推荐使用双指针）
10、18 四数之和

六、栈与队列（栈和队列都是容器适配器）

参考理论

参考理论：栈与队列理论基础

栈里面的元素在内存中是连续分布的么？
这个问题有两个陷阱：
陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。

数据结构学习（queue、stack、deque）：

queue<int> q;
stack<int> s;
deque<int> d;// 1、queue- front()	// 返回队列中的第一个元素int q1 = q.front();- back()  // 返回队列中最后一个元素int q2 = q.front();- push()  // 在队尾插入一个元素q.push(2);		// 在队尾插入一个元素2- pop()   // 删除队列第一个元素q.pop();- size()  // 返回队列中元素个数- empty() // 如果队列空则返回true// 2、stack- top()	// 返回最后一个安插的元素(返回栈顶元素)- int s1 = s.top();- push()	// 安插一个元素(操作同queue)- pop()	// 移除容器内的下一个元素(操作同queue)- size()  // 返回队列中元素个数- empty() // 如果队列空则返回true// 3、deque(双端队列，大部分常用用法和vector一样)，区别如下：// deque相比于vector，多了push_front()、pop_front()// push_front()：插入元素到容器起始 d.push_front(1);	// 插入1到容器起始// pop_front()：移除容器首元素d.pop_front();// 【注】：string和vector用法基本相同

例题

1、232 用栈实现队列
2、225 用队列实现栈
3、20 有效的括号

括号不匹配的三种情况：
1、第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
2、第二种情况，字符串里右方向的括号多余了，所以不匹配。
3、第三种情况，括号没有多余，但是括号的类型没有匹配上。

4、1047 删除字符串中的所有相邻重复项
5、150 逆波兰表达式求值（类似于：1047 删除字符串中的所有相邻重复项）

例子：( 1 + 2 ) * ( 3 + 4 )
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：
1、去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果；
2、适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

6、239 滑动窗口最大值

// 需要的队列应该长这个样子：
class MyQueue {
public:void pop(int value) {}void push(int value) {}int front() {return que.front();}
};

设计单调队列的时候，pop，和push操作要保持如下规则：
1、pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作；
2、push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

// 代码如下：
class Solution {
private:class myQueue {public:deque<int> que;void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {myQueue Que;vector<int> result;for (int i = 0; i < k; ++i) {Que.push(nums[i]);}result.push_back(Que.front());for (int i = k; i < nums.size(); ++i) {Que.pop(nums[i - k]);Que.push(nums[i]);result.push_back(Que.front());}return result;}
};
// 【注】：myQueue Que;执行后，
//		 就声明了一个deque<int> que;
//    	 只要myQueue Que不销毁，双端队列que是一直存在的，
//		 所有对双端队列que进行的操作，都是在原来的基础上进行的。

7、347 前 K 个高频元素

使用一种容器适配器：优先级队列

一：什么是优先级队列呢？
答：1、其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
2、而且优先级队列内部元素是自动依照元素的权值排列。
二：那么它是如何有序排列的呢？
答：缺省情况下，priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
三：什么是堆呢？
答：堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
*
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用**priority_queue（优先级队列）**就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。
为什么不用快排呢？ 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

小顶堆、大顶堆例子：

// 大顶堆例1std::priority_queue<int, std::vector<int>> pri_que;pri_que.push(3);pri_que.push(2);pri_que.push(1);std::cout << pri_que.top() << std::endl;	// 输出为：3
// 大顶堆例2std::priority_queue<int, std::vector<int>> pri_que;pri_que.push(3);pri_que.push(2);pri_que.push(5);std::cout << pri_que.top() << std::endl;	// 输出为：5// 小顶堆例1（与大顶堆区别在于第三个位置，即：小顶堆为std::greater<int>）std::priority_queue<int, std::vector<int>, std::greater<int>> pri_que;pri_que.push(3);pri_que.push(2);pri_que.push(1);std::cout << pri_que.top() << std::endl;	// 输出为：1
// 小顶堆例2std::priority_queue<int, std::vector<int>, std::greater<int>> pri_que;pri_que.push(3);pri_que.push(2);pri_que.push(5);std::cout << pri_que.top() << std::endl;	// 输出为：2//------------------------------------------------------------// 本题用自定义的小顶堆
class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
/*
此类常规写法为：
class mycomparison {
public:bool operator()(const int& lhs, const int& rhs) {return lhs > rhs;}
};
对应定义：
std::priority_queue<int, std::vector<int>, mycomparison> pri_que;
*/
// 对频率排序，定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

本题代码：

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

例外题：
71 简化路径

七、二叉树

参考理论

参考理论：二叉树理论基础篇

//	链式存储的二叉树节点的定义方式
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

递归三步（有回溯的思路就往递归上靠）

1、确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2、确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3、确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

例题

在实现迭代法的过程中，有同学问了：递归与迭代究竟谁优谁劣呢？
1、从时间复杂度上其实迭代法和递归法差不多（在不考虑函数调用开销和函数调用产生的堆栈开销），但是空间复杂度上，递归开销会大一些，因为递归需要系统堆栈存参数返回值等等。
2、递归更容易让程序员理解，但收敛不好，容易栈溢出。
3、这么说吧，递归是方便了程序员，难为了机器（各种保存参数，各种进栈出栈）。
4、在实际项目开发的过程中我们是要尽量避免递归！因为项目代码参数、调用关系都比较复杂，不容易控制递归深度，甚至会栈溢出。
【注】： 在递归中，如果需要一层层回溯结果还是要另写一个函数编写相应逻辑。

1、二叉树的遍历（适合递归遍历）：
1.1、递归遍历：
144 二叉树的前序遍历、145 二叉树的后序遍历、94 二叉树的中序遍历

技巧：这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式：
1、前序遍历：中左右
2、中序遍历：左中右
3、后序遍历：左右中

1.2、迭代遍历：
144 二叉树的前序遍历、145 二叉树的后序遍历、94 二叉树的中序遍历
2、二叉树层序遍历登场！（适合迭代遍历）
2.1、102 二叉树的层序遍历

//	层序遍历模板-------------------------------------------------------------------------------------
//	迭代法：
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};//	递归法
class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

//	vector语法学习
vector<vector<int>> vec;		//	1、创建了一个实体为vertor<int>的容器，可以理解为一个二维数组
vec.push_back(vector<int>());	//	2、相当于分隔符，往二维数组里插入空的vector<int>()，可以理解为分行，即二维数组的下一行
vec.back().push_back();			//	3、在最后一行末插入数据
vec[n].push_back();				//	4、在指定行末插入数据
vec.push_back(res);		        //	5、其中vec可以为二维数组，res为一维数组（vector<int> res;）

2.2、107 二叉树的层序遍历 II

//	二维数组的注意点
//	现有二维数组result，数据如下：
result = [[3], [9, 20], [6, 8, 15, 7]];
reverse(result.begin(), result.end());
//	则result变为：（注意；一维里面的数据不会进行翻转）
result = [[6, 8, 15, 7], [9, 20], [3]]；

2.3、199 二叉树的右视图
2.4、637 二叉树的层平均值
2.5、429 N 叉树的层序遍历

/*
N叉树定义：
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*///	访问一个N叉树的孩子节点
TreeNode* node；
node -> children.size()；	// 访问孩子节点的个数
node -> children[i]；	    // 0 <= i < node -> children.size()（遍历访问node节点的孩子节点）

2.6、515 在每个树行中找最大值
2.7、116 填充每个节点的下一个右侧节点指针
2.8、117 填充每个节点的下一个右侧节点指针 II
2.9、104 二叉树的最大深度
2.10、111 二叉树的最小深度
3、226 翻转二叉树

// 递归法
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);  // 中，root -> left == NULL || root -> right == NULL也成立invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};
// 迭代法
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;stack<TreeNode*> st;st.push(root);while(!st.empty()) {TreeNode* node = st.top();              // 中st.pop();swap(node->left, node->right);if(node->right) st.push(node->right);   // 右if(node->left) st.push(node->left);     // 左}return root;}
};

周总结：
推荐题：
1、589 N 叉树的前序遍历
2、590 N 叉树的后序遍历

4、101 对称二叉树

相似例题：
1、100 相同的树
2、572 另一棵树的子树

// 572 另一棵树的子树代码细节：
class Solution {
public:bool compare(TreeNode* rot, TreeNode* subRot) {if (rot == nullptr && subRot != nullptr) return false;else if (rot != nullptr && subRot == nullptr) return false;else if (rot == nullptr && subRot == nullptr) return true;else if (rot -> val != subRot -> val) return false;bool rootleft = compare(rot -> left, subRot -> left);bool rootright = compare(rot -> right, subRot -> right);bool isSame = rootleft && rootright;return isSame;}bool dfs(TreeNode* o, TreeNode* t) {if (o == nullptr) {return false;}return compare(o, t) || dfs(o -> left, t) || dfs(o -> right, t);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if (root == nullptr && subRoot == nullptr) return true;return dfs(root, subRoot);}
};

5、559 N 叉树的最大深度
6、222 完全二叉树的节点个数

【注】：
1、满二叉树属于完全二叉树；
2、普通二叉树用层序遍历；
3、完全二叉树用递归。

7、110 平衡二叉树
针对二叉树深度和高度的理解：

所用遍历逻辑：
1、求深度： 从上到下去查，所以需要前序遍历（中左右）；或者用层序遍历（迭代）；
2、求高度： 从下到上去查，所以只能后序遍历（左右中）。

// 下面以二叉树的最大深度为例
// 1、以根节点高度的逻辑（后序遍历）
class solution {
public:int getdepth(treenode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left);       // 左int rightdepth = getdepth(node->right);     // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}int maxdepth(treenode* root) {return getdepth(root);}
};
// 2、以叶子节点深度的逻辑（前序遍历）
class solution {
public:int result;void getdepth(treenode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左depth++;    // 深度+1getdepth(node->left, depth);depth--;    // 回溯，深度-1}if (node->right) { // 右depth++;    // 深度+1getdepth(node->right, depth);depth--;    // 回溯，深度-1}return ;}int maxdepth(treenode* root) {result = 0;if (root == NULL) return result;getdepth(root, 1);return result;}
};

8、257 二叉树的所有路径
9、404 左叶子之和
10、513 找树左下角的值
11、
举例来详细说明：递归函数什么时候要有返回值
1、112 路径总和

// 1 递归终止条件判断为空
if ("判断当前节点是否为空") return; // 递归终止条件
...
进行递归; // 不用if进行判断// 2 递归终止条件不是判断空
// 因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
if ("判断叶子节点") return; // 递归终止条件
...
if ("不为空") 进行递归; // 要if进行判断，在进行递归

2、113 路径总和 II

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：（详细）
1、 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（113、路径总和 II）
2、 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。（236、二叉树的最近公共祖先 ）
3、 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112、路径总和）

12、106 从中序与后序遍历序列构造二叉树
13、105 从前序与中序遍历序列构造二叉树

切割坚持左闭右开的原则。

14、654 最大二叉树

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

// 版本一：
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* node = new TreeNode(0);if (nums.size() == 1) {node->val = nums[0];return node;}// 找到数组中最大的值和对应的下标int maxValue = 0;int maxValueIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxValueIndex = i;}}node->val = maxValue;// 最大值所在的下标左区间 构造左子树if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);}// 最大值所在的下标右区间 构造右子树if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);}return node;}
};
// 版本二：
class Solution {
private:// 在左闭右开区间[left, right)，构造二叉树TreeNode* traversal(vector<int>& nums, int left, int right) {if (left >= right) return nullptr;// 分割点下标：maxValueIndexint maxValueIndex = left;for (int i = left + 1; i < right; ++i) {if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;}TreeNode* root = new TreeNode(nums[maxValueIndex]);// 左闭右开：[left, maxValueIndex)root->left = traversal(nums, left, maxValueIndex);// 左闭右开：[maxValueIndex + 1, right)root->right = traversal(nums, maxValueIndex + 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};

如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

15、617 合并二叉树
16、700 二叉搜索树中的搜索

二叉搜索树是一个有序树：
1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3、它的左、右子树也分别为二叉搜索树

17、98 验证二叉搜索树

解题思路：中序遍历下，输出的二叉搜索树节点的数值是有序序列。
这道题目比较容易陷入两个陷阱：
1、 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
2、 见代码随想录。

18、530 二叉搜索树的最小绝对差

改题展示了，在递归中如何记录前一个节点的指针。

19、501 二叉搜索树中的众数

sort自定义排序

//	例1：
// map中的value排个序；
// 有的同学可能可以想直接对map中的value排序，还真做不到，C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序；
// 所以要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; // 按照频率从大到小排序
}
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序//	例2：
// 按从大到小排
static bool cmp(int a, int b) {return a > b;
}
int main() {vector<int> A{1, 8, 7, 6, 9};	//	 A内的元素为：1, 8, 7, 6, 9//	二维情况：vector<vector<int>> test2{{1,2,3,4,5,6,7},{1,2,3,4,5,6}};sort(A.begin(), A.end(), cmp);	// A内的元素为：9，8，7，6，1return 0;
}// 例3：
// 按从大到小排
static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] > b[0];
}
int main() {vector<vector<int>> people;  // people内的定义：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]...sort (people.begin(), people.end(), cmp);...return 0;
}

参考文章：C++的vector的使用

20、236 二叉树的最近公共祖先

归纳总结：
1、 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯） 实现从低向上的遍历方式。
2、 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
3、 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

21、235 二叉搜索树的最近公共祖先

对于二叉搜索树，只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。

22、701 二叉搜索树中的插入操作
23、450 删除二叉搜索树中的节点

二叉搜索树中删除节点有以下五种情况：
第一种情况： 没找到删除的节点，遍历到空节点直接返回了
找到删除的节点：
第二种情况： 左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况： 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况： 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况： 左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

faction (TreeNode * root) {TreeNode* cur = root->right;cur->left = root->left; // 对二叉树进行这样的赋值是对地址直接进行操作（即：只是对树的结构进行变换，而非new新的节点），而非拷贝
}// 树节点的移动(找到树的最左边的节点)
TreeNode* cur = root -> left;
while(cur->left != nullptr) {cur = cur->left;
}
// 此时cur为树的最左边的节点

24、669 修剪二叉搜索树
25、108 将有序数组转换为二叉搜索树

int mid = (left + right) / 2，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，所以可以这么写：int mid = left + ((right - left) / 2)。

26、538 把二叉搜索树转换为累加树

大总结：

1、 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
2、 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
3、 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

借用大佬的图片：

八、动态规划

参考理论

参考理论：动态规划理论基础

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

动态规划问题五步曲：

1. 第一步：确定dp数组（dp table）以及下标的含义
2. 第二步：确定递推公式
3. 第三步：dp数组如何初始化
4. 第四步：确定遍历顺序
5. 第五步：举例推导dp数组

【注】：
1、做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
2、然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
3、如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
4、如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

灵魂三问：
1、这道题目我举例推导状态转移公式了么？
2、我打印dp数组的日志了么？
3、打印出来了dp数组和我想的一样么？

例题

基础题型

1、509 斐波那契数
2、70 爬楼梯

到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

3、746 使用最小花费爬楼梯
4、62 不同路径
5、63 不同路径 II
6、343 整数拆分

j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j] 是拆分成两个以及两个以上的个数相乘。

7、96 不同的二叉搜索树

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
> 所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

背包问题（求数量、次数）

求装满背包有几种方法，递归公式都是一样的，没有什么差别，但关键在于遍历顺序！

参考理论（01背包）

参考理论1：动态规划：关于01背包问题，你该了解这些！
参考理论2：动态规划：关于01背包问题，你该了解这些！（滚动数组）

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
【注】：01背包的dp数组初始化为0就可以。因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

// 代码如下：
for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}
}

对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。【图片参考大佬】

例题：
1、416 分割等和子集

只有确定了如下四点，才能把01背包问题套到本题上来。
1、背包的体积为sum / 2
2、背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
3、背包如果正好装满，说明找到了总和为 sum / 2 的子集。
4、背包中每一个元素是不可重复放入。
【注】：本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

2、1049 最后一块石头的重量 II

本题物品的重量为store[i]，物品的价值也为store[i]。

3、494 目标和

假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = S
x = (S + sum) / 2
此时问题就转化为，装满容量为x背包，有几种方法。

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。求组合类问题的公式，都是类似这种：dp[j] += dp[j - nums[i]]

4、474 一和零

本题中strs数组里的元素就是物品，每个物品都是一个！
而m和n相当于是一个背包，两个维度的背包。

参考理论（完全背包）

参考理论：动态规划：关于完全背包，你该了解这些！

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历。
【注1】：完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）
【注2】：对于组合问题（或者排列问题）， 两个for循环的要有明确的先后循序，见518 零钱兑换 II（组合：先物品、后背包）、377 组合总和 Ⅳ（排列：先背包、后物品）。

5、518 零钱兑换 II

本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的组合数！
dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
所以递推公式：dp[j] += dp[j - coins[i]];

重点：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

6、377 组合总和 Ⅳ

弄清什么是组合，什么是排列很重要。
本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！
确定递推公式： dp[i] += dp[i - nums[j]]; dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
本题与动态规划：518.零钱兑换II就是一个鲜明的对比，一个是求排列，一个是求组合，遍历顺序完全不同。

7、70 爬楼梯

改为：一步一个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

8、322 零钱兑换

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。

9、279 完全平方数

把题目翻译一下： 完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

10、139 单词拆分

本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环。
如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的子串都预先放在一个容器里。
所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。

参考理论（多重背包）

参考理论：动态规划：关于多重背包，你该了解这些！

背包总结（五星推荐）

总结篇

打家劫舍

1、198 打家劫舍

决定dp[i]的因素就是第i房间偷还是不偷

2、213 打家劫舍 II
3、337 打家劫舍 III

树形dp

股票问题

1、121 买卖股票的最佳时机
2、122 买卖股票的最佳时机 II
3、123 买卖股票的最佳时机 III

一天一共就有五个状态：
1、没有操作
2、第一次买入
3、第一次卖出
4、第二次买入
5、第二次卖出
需要注意： dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

4、188 买卖股票的最佳时机 IV

强调一下： dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

5、309 最佳买卖股票时机含冷冻期

具体可以区分出如下四个状态：
1、状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
卖出股票状态，这里就有两种卖出股票状态
2、状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
3、状态三：今天卖出了股票
4、状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

6、714 买卖股票的最佳时机含手续费

子序列问题（掌握的不好）

1、300 最长递增子序列

不连续

2、674 最长连续递增序列

连续

3、718 最长重复子数组

子数组： 是从原数组截取连续的子数组。

4、1143 最长公共子序列

子序列： 本题和动态规划：718 最长重复子数组区别在于这里不要求是连续的了，但要有相对顺序，即：“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

5、1035 不相交的线

本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

6、53 最大子数组和
7、392 判断子序列

这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。
所以掌握本题也是对后面要讲解的编辑距离的题目打下基础。

8、115 不同的子序列【这题看解释，还是有点懵】
9、583 两个字符串的删除操作
10、72 编辑距离

word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样！

392 判断子序列、
115 不同的子序列、
583 两个字符串的删除操作、
72 编辑距离
归为一类题。

11、647 回文子串
12、516 最长回文子序列

回文子串是要连续的，回文子序列可不是连续的！
回文子串，补充题：
5 最长回文子串

参考博客：
1、动态规划学习
2、算法-动态规划 Dynamic Programming–从菜鸟到老鸟
3、告别动态规划，连刷40道动规算法题，我总结了动规的套路
4、力扣刷题记录 （七）动态规划（一）基础题目
5、力扣刷题记录 （七）动态规划（二）背包问题
6、力扣刷题记录 （七）动态规划（三）打家劫舍
7、力扣刷题记录 （七）动态规划（四）股票系列
8、力扣刷题记录 （七）动态规划（五）子序列系列

九、回溯

参考理论

参考理论：回溯算法理论基础

做回溯要先画树形图

三部曲：

1. 第一步：回溯函数模板返回值以及参数 ——回溯算法中函数返回值一般为void
2. 第二步：回溯函数终止条件 ——终止条件不一样，可能只有一个，也可能会有多个
3. 第三步：单层搜索的过程——循环里要处理的内容

总模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}// 一个for循环代表树形结构的一层信息for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

去重注意点：

组合问题和子集问题的去重要先排序（sort），排列问题不用排序

【注】： 原因在于集合内的元素不存在先后顺序，具体原因，见下图：

1 组合问题

递归实现二进制枚举（子集枚举）模板：

vector<int> temp;
void dfs(int cur, int n) {if (cur == n + 1) {// 记录答案// ...return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur + 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur + 1, n, k);
}

组合枚举模板：

例如我们需要在n个元素选k个，在dfs的时候需要多传入一个参数 k，即dfs(cur，n，k)。在每次进入这个dfs函数时，我们都去判断当前temp的长度是否为k，如果为k，就把temp加入答案并直接返回，模板如下：

vector<int> temp;
void dfs(int cur, int n) {// 记录合法的答案if (temp.size() == k) {ans.push_back(temp);return;}// cur == n + 1 的时候结束递归if (cur == n + 1) {return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur + 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur + 1, n, k);
}

例题

1、77 组合
2、39 组合总和
3、40 组合总和 II
4、216 组合总和 III
5、17 电话号码的字母组合

什么时候需要startIndex呢？
1、 如果是一个集合来求组合的话，就需要startIndex，例如：77.组合、216.组合总和III；
2、 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合。

2 切割问题

这里是枝干写过程，根结点写字符串剩余的字符
切割问题和组合问题的区别：
1、 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。
2、 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。

例题：
1、131 分割回文串
2、93 复原 IP 地址【重点】

3 子集问题

1、78 子集
2、90 子集II
3、491 递增子序列

unordered_set< int > uset;
uset.insert(10); // 插入元素

4 全排列

1、46 全排列
2、47 全排列 II

5 其他

1、332 重新安排行程

这道题目有几个难点：
1、 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2、 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
3、 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4、 搜索的过程中，如何遍历一个机场所对应的所有机场。

// 使用的数据结构
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;  // map:自动对数据进行排序的容器
// 有tickets 
vector<vector<string>> tickets = [["MUC","LHR"],["JFK","MUC"]];
// 记录映射关系
for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++; // 记录映射关系
}

2、51 N 皇后
3、37 解数独

总结

1、一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

参考大佬：
1、力扣题型总汇——回溯算法
2、Leetcode 回溯算法（一）
3、代码随想录、对应视频

十、贪心算法

参考理论

参考理论：关于贪心算法，你该了解这些！

贪心的本质： 是选择每一阶段的局部最优，从而达到全局最优。
1、问：如何能看出局部最优是否能推出整体最优呢？
答： 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
2、问： 如何验证可不可以用贪心算法呢？
答： 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心一般解题步骤（4步骤）：
1、 将问题分解为若干个子问题
2、 找出适合的贪心策略
3、 求解每一个子问题的最优解
4、 将局部最优解堆叠成全局最优解
【注】：其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

例题

1、455 分发饼干

可以尝试使用贪心策略，先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

2、376 摆动序列

实际操作上，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

3、53 最大子数组和

局部最优： 当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优： 选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

4、122 买卖股票的最佳时机 II

本题首先要清楚两点：
1、 只有一只股票！
2、 当前只有买股票或者卖股票的操作
【注】：想获得利润至少要两天为一个交易单元。

---

分析： 假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]，相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！ 如果正利润连续上了，相当于连续持有股票，而本题并不需要计算具体的区间。

5、55 跳跃游戏

贪心算法局部最优解： 每次取最大跳跃步数（取最大覆盖范围）；
整体最优解： 最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！

6、45 跳跃游戏 II

理解本题的关键在于： 以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最小步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

7、1005 K 次取反后最大化的数组和

思路：
1、 局部最优： 让绝对值大的负数变为正数，当前数值达到最大，全局最优： 整个数组和达到最大。
【注】：那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。
2、 局部最优： 只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1得到-1比反转5得到的-5大多了），全局最优： 整个数组和达到最大。

8、134 加油站

贪心算法（方法一）
直接从全局进行贪心选择，情况如下：
情况一： 如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的;
情况二： rest[i] = gas[i] - cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点;
情况三： 如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。
贪心算法（方法二）
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。 每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
局部最优： 当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。
全局最优： 找到可以跑一圈的起始位置。

9、135 分发糖果

这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
分两种情况：
1、先确定右边评分大于左边的情况（也就是从前向后遍历）：
局部最优： 只要右边评分比左边大，右边的孩子就多一个糖果，全局最优： 相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果；
2、再确定左孩子大于右孩子的情况（从后向前遍历）：
局部最优： 取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优： 相邻的孩子中，评分高的孩子获得更多的糖果。

10、860 柠檬水找零

局部最优： 遇到账单20，优先消耗美元10，完成本次找零。全局最优： 完成全部账单的找零。

11、406 根据身高重建队列

在135 分发糖果就强调过一次，遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

// 版本一
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);	//	people[i]取二维数组的第i行元素，插入que的position处}return que;}
};

12、452 用最少数量的箭引爆气球

局部最优： 当气球出现重叠，一起射，所用弓箭最少。全局最优： 把所有气球射爆所用弓箭最少。

13、435 无重叠区间

右边界排序之后，局部最优： 优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优： 选取最多的非交叉区间。

14、763 划分字母区间
15、56 合并区间

按照左边界排序，排序之后 局部最优： 每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优： 合并所有重叠的区间。

16、738 单调递增的数字

局部最优： 遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优： 得到小于等于N的最大单调递增的整数。

17、714 买卖股票的最佳时机含手续费
18、968 监控二叉树

所以我们要从下往上看，局部最优： 让叶子节点的父节点安摄像头，所用摄像头最少；
整体最优： 全部摄像头数量所用最少！

十一、单调栈

使用场景

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
单调栈的本质：空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。

在使用单调栈的时候首先要明确如下几点：
1、单调栈里存放的元素是什么？
答： 单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
2、单调栈里元素是递增呢？ 还是递减呢？
答： 注意一下顺序为 从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定会越看越懵

例题

1、739 每日温度

本题其实就是找到一个元素右边第一个比自己大的元素。

2、496 下一个更大元素 I

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。
可能这里有一些同学不理解，那么可以自己尝试一下用递减栈，能不能求出来。其实递减栈就是求右边第一个比自己小的元素了。

3、503 下一个更大元素 II
4、42 接雨水
5、84 柱状图中最大的矩形

记录每个柱子左边第一个小于该柱子的下标