给定一个长度为 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;
}

给你一个整数数组 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的结果，直接返回resif (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;}
};

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，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());}
};

给定一个包含红色、白色和蓝色、共 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--;}}}
};