11.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
本题通过双指针来解决，左指针从左端点开始和右指针从右端点开始，如果左指针的高度比右指针的高度低，则将左指针向右一步，否则右指针向左一步，知道两指针相遇。
int maxArea(vector<int>& height) {
int l = 0, r = height.size()-1;
int res = 0;
while(l < r) {
res = max(res, (r - l) * min(height[l], height[r]));
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return res;
}
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
这里可能属于三指针的范畴，但是我们依然可以用双指针的做法来解决
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size()-1; i++) {
// 如果排序后第i个数大于0，那么不可能后面有加起来为0的结果，直接返回res
if (nums[i] > 0) {
return res;
}
// 判断是否重复
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int l = i + 1;
int r = nums.size()-1;
while(l < r) {
if(nums[l] + nums[r] + nums[i] > 0) {
// 消除重复
while(l < r && nums[r] == nums[r-1]){
r--;
}
r--;
} else if (nums[l] + nums[r] + nums[i] < 0) {
// 消除重复
while(l < r && nums[l] == nums[l+1]) {
l++;
}
l++;
} else {
res.push_back({nums[i], nums[l], nums[r]});
// 消除重复
while(l < r && nums[l] == nums[l+1]) {
l++;
}
// 消除重复
while(l < r && nums[r] == nums[r-1]) {
r--;
}
l++;
r--;
}
}
}
return res;
}
};
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
// 1. 从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
// 2. 在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
// 3. 将 A[i] 与 A[k] 交换
// 4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
// 5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int j = -1;
int i;
for(i=nums.size()-1; i-1>=0; i--){
if (nums[i] > nums[i-1]) {
j = i;
i = j-1;
break;
}
}
if (j == -1) {
reverse(nums.begin(), nums.end());
return;
}
int k;
for(k=nums.size()-1; k>=j; k--) {
if(nums[k] > nums[i]) {
swap(nums[k], nums[i]);
break;
}
}
reverse(nums.begin()+j, nums.end());
}
};
75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
这是一个荷兰旗问题，我们可以用双指针的办法解决。
class Solution {
public:
// L及L的左边都是0，R及R的右边都是2，
// 单指针刷过去，如果遇到0，就跟L调换，并将L向右移
// 如果遇到2,就跟R调换，R向左移，但是i也需要在停留在当前进行判断
void sortColors(vector<int>& nums) {
int L = 0, R = nums.size()-1;
for(int i=0; i<=R; i++) {
if (nums[i] == 0) {
swap(nums[i], nums[L]);
L++;
}
else if (nums[i] == 2) {
swap(nums[i], nums[R]);
R--;
i--;
}
}
}
};
